poj 2502（floyd）

题意：从家到学校，可以步行，可以地铁，最少时间？典型的最短路径。

注意三点地方：

一、每两点可达，即使没有地铁，也可以步行的；

二、相邻地铁可达，不相邻不用管（即在同一条地铁线上的两个不相邻站台不用管）；

三、地铁线不一定是直的。（WA了好两次）

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 #define inf 0x7ffffff
 6 #define eps 1e-8
 7 #define MIN(x,y) ((x)>(y)?(y):(x))
 8 
 9 int V;
10 struct node
11 {
12     double x,y;
13 }pos[210];
14 
15 double dis[210][210];//i->j最短时间
16 
17 void floyd()
18 {
19     for(int k=0;k<V;k++) 
20         for(int i=0;i<V;i++)
21             for(int j=0;j<V;j++)
22                 dis[i][j]=MIN(dis[i][j],dis[i][k]+dis[k][j]);
23 }
24 
25 double subwaydis(node a,node b)
26 {
27     double d=sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
28     return d/40.0;
29 }
30 
31 double walkway(node a,node b)
32 {
33     double d=sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
34     return d/10.0;
35 }
36 int main()
37 {
38     int x,y;
39     scanf("%d%d",&x,&y);
40     V=0;
41     pos[V].x=x/1000.0,pos[V++].y=y/1000.0;
42     scanf("%d%d",&x,&y);
43     pos[V].x=x/1000.0,pos[V++].y=y/1000.0;
44     for(int i=0;i<210;i++)
45         for(int j=0;j<210;j++)
46             if(i==j)
47                 dis[i][j]=0;
48             else
49                 dis[i][j]=dis[j][i]=inf;
50 
51     while(scanf("%d%d",&x,&y) != EOF)
52     {
53         int st=V;
54         while(x!=-1 && y!=-1)
55         {
56             pos[V].x=x/1000.0,pos[V++].y=y/1000.0;
57             scanf("%d%d",&x,&y);
58         }
59 
60         for(int i=st;i<V-1;i++)
61                 dis[i][i+1]=dis[i+1][i]=subwaydis(pos[i],pos[i+1]);
62     }
63     //cout<<V<<endl;
64     //for(int i=0;i<V;i++)
65     //    for(int j=0;j<V;j++)
66     //        cout<<"i="<<i<<" j="<<j<<" "<<dis[i][j]<<endl;
67     
68     for(int i=0;i<V;i++)
69         for(int j=0;j<V;j++)
70             if(fabs(dis[i][j]-inf)<=eps)
71                 dis[i][j]=walkway(pos[i],pos[j]);
72     floyd();
73     double ans=(dis[0][1]*60.0);
74     printf("%.0lf\n",(ans));
75     return 0;
76 }