POJ 2502 Subway（将各种数据转化成图+最短路+迪杰斯特拉算法）

蔚落 2022-06-11 02:09 50阅读 0赞

You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want to be late for class, you want to know how long it will take you to get to school.  
You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch between different subway lines if you wish. All subway lines go in both directions.

Input

Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each stop on the line, in order. You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres. Each line has at least two stops. The end of each subway line is followed by the dummy coordinate pair -1,-1. In total there are at most 200 subway stops in the city.

Output

Output is the number of minutes it will take you to get to school, rounded to the nearest minute, taking the fastest route.

Sample Input

0 0 10000 1000
    0 200 5000 200 7000 200 -1 -1 
    2000 600 5000 600 10000 600 -1 -1

Sample Output

题解：

这题是我这场比赛做过最有意思的一题，wa了8次才过。。发现了一个很坑的地方，就是每一条铁路线上，假设有n个点，那么只能形成n-1条边。。体会一下，比如求首位两站的时间，接首尾连起来用距离除以40这个算出来是错的，因为铁路可能是弯的！！我后来意识到了这点改了一下就ac了。。还有要注意一点就是除了铁路线之间形成的边是除以40，其他的点互相直接连接都是除以10计算，设dis是两点间直线距离，怕覆盖掉就改成min(p\[i\]\[j\],dis/10)，就好了，然后经过老刘的一系列单位换算，得出最后答案乘3.6除60就是分钟数，注意G++交要%f，这里因为%.0f自带四舍五入就不用操心了

ps：

因为当时wa得慌了。。本来应该把算直线距离的公式写成函数可以漂亮很多简洁很多的qaq

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    const double INF=200861111;
    int vis[305];//存迪杰斯特拉是否遍历过该节点
    double p[305][305];//存图
    double dis[305];//存距离1的距离
    double dx[305];//存当前铁路每个点的x坐标
    double dy[305];//存当前铁路每个点的y坐标
    double xx[305];//存各个点的x坐标
    double yy[305];//存各个点的y坐标
    int main()
    {
        int i,j,k,n,m,tot=3,d,ans=0,sum,key;
        double sx,ex,sy,ey,minn;
        for(i=1;i<=220;i++)
            for(j=1;j<=220;j++)
              {
                  if(i==j)
                    p[i][j]=0;
                  else
                    p[i][j]=INF;//初始化
              }
        scanf("%lf%lf%lf%lf",&sx,&sy,&ex,&ey);
        p[1][2]=sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey))/10;//记出发点为1
        p[2][1]=sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey))/10;//记结束点为2
        xx[1]=sx;
        yy[1]=sy;
        xx[2]=ex;
        yy[2]=ey;
        while(scanf("%lf%lf",&dx[ans],&dy[ans])!=EOF)
        {
            if(dx[ans]==-1&&dy[ans]==-1)
            {
                tot+=ans;
                ans=0;
                continue;
            }
            if(ans!=0)
            {
                p[tot+ans][tot+ans-1]=sqrt((dx[ans]-dx[ans-1])*(dx[ans]-dx[ans-1])+(dy[ans]-dy[ans-1])*(dy[ans]-dy[ans-1]))/40;
                p[tot+ans-1][tot+ans]=sqrt((dx[ans]-dx[ans-1])*(dx[ans]-dx[ans-1])+(dy[ans]-dy[ans-1])*(dy[ans]-dy[ans-1]))/40;//记录时间
            }
            xx[tot+ans]=dx[ans];
            yy[tot+ans]=dy[ans];
            ans++;
        }
        for(i=1;i<tot;i++)
        {
            for(j=1;j<tot;j++)
            {
                p[i][j]=p[j][i]=min(p[i][j],sqrt((xx[i]-xx[j])*(xx[i]-xx[j])+(yy[i]-yy[j])*(yy[i]-yy[j]))/10);//记录到各点步行的时间
            }
        }
        memset(vis,0,sizeof(vis));初始化为0
        for(i=1;i<tot;i++)
            dis[i]=INF;
        dis[1]=0;
        for(i=1;i<tot-1;i++)//迪杰斯特拉算法
        {
            minn=INF;
            for(j=1;j<tot;j++)
            {
                if(!vis[j]&&minn>dis[j])
                {
                    minn=dis[j];
                    key=j;
                }
            }
            if(minn==INF)
                break;
           vis[key]=1;
            for(j=1;j<tot;j++)
            {
                if(minn+p[key][j]<dis[j])
                {
                    dis[j]=minn+p[key][j];
                }
            }
        }
        printf("%.0f\n",dis[2]*3.6/60);//由于老刘神奇的单位换算得到
        return 0;
    }