Subway（建图 + dijkstra算法）

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

21

题意：给了一个学生的家，学校，以及地铁线路各站的坐标。规定步行10km/h ，坐地铁40km/h，他到达地铁站的时候地铁正好发车，问最少需要多次时间学生能从家到学校。

思路：我们可以用邻接矩阵储存各点之间所需的时间，然后通过dijkstra算法求出最短时间。这道题需要注意的是创建矩阵的时候咬咬注意每条地铁线路的地铁站只能相互到底，且可以从每个地铁站直接步行到学校。

代码如下：

#include<cstdio>
#include<cmath>
#include<cstring>
#define inf 0x3f3f3f3f
int book[210];
double map[210][210],dis[210];
struct node
{
    double x,y;
}list[220];
int main()
{
    double tx,ty;
    while(~scanf("%lf%lf%lf%lf",&list[1].x,&list[1].y,&tx,&ty))//起点，终点
    {
        int i=2,j;
        memset(book,0,sizeof(book));  //初始化
        memset(map,0,sizeof(map));
        while(~scanf("%lf%lf",&list[i].x,&list[i].y))//每条地铁线路
        {
            while(1)
            {
                j=i;
                i++;
                scanf("%lf%lf",&list[i].x,&list[i].y);
                if(list[i].x==-1&&list[i].y==-1)
                   break;            //计算每段地铁路线的距离
                double d=sqrt((list[i].x-list[j].x)*(list[i].x-list[j].x)+(list[i].y-list[j].y)*(list[i].y-list[j].y)+0.0);
                double t=(d/40000.0)*60;//计算每条线路，各端的时间
                map[i][j]=map[j][i]=t;
            }
        }
        int n=i;
        list[n].x=tx;
        list[n].y=ty;
        for(i=1;i<=n;i++)//计算步行所需的时间
        {
            for(j=i+1;j<=n;j++)
            {
               if(!map[i][j])
               {
                   double d=sqrt((list[i].x-list[j].x)*(list[i].x-list[j].x)+(list[i].y-list[j].y)*(list[i].y-list[j].y)+0.0);
                   double t=(d/10000.0)*60;
                   map[i][j]=map[j][i]=t;
               }
            }
        }
        for(i=1;i<=n;i++)
            dis[i]=map[1][i];
        dis[i]=0;
        book[1]=1;
        int k;
        for(i=1;i<=n;i++)  //dijkstra算法
        {
            double minn=inf;
            for(j=1;j<=n;j++)
            {
                if(!book[j]&&dis[j]<minn)
                {
                    minn=dis[j];
                    k=j;
                }
            }
            if(minn==inf)
                break;
            book[k]=1;
            for(j=1;j<=n;j++)
                if(!book[j]&&dis[j]>minn+map[k][j])
                    dis[j]=minn+map[k][j];
        }
        int tt=int(dis[n]+0.5);//四舍五入
        printf("%d\n",tt);
    }
}