1 //Accepted    504 KB    16 ms  2 //spfa最短路  3 //把n个地铁站作为n个顶点，边权为从一个站到另一个站的时间  4 //注意：地铁在相邻的两站之间是直线行驶，但其他的就不是了  5 #include <cstdio>  6 #include <cstring>  7 #include <iostream>  8 #include <queue>  9 #include <cmath> 10 #include <algorithm> 11 using namespace std; 12 /** 13   * This is a documentation comment block 14   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 15   * @authr songt 16   */ 17 const int imax_n = 205; 18 const double inf = 1000000000000000000.0; 19 double x[imax_n]; 20 double y[imax_n]; 21 double a[imax_n][imax_n]; 22 double dis[imax_n]; 23 bool vis[imax_n]; 24 int n; 25 double getDis(double x1,double y1,double x2,double y2) 26 { 27     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); 28 } 29 void init() 30 { 31     for (int i=1;i<=n;i++) 32     { 33         for (int j=1;j<=n;j++) 34         { 35             if (fabs(a[i][j])<1e-9) 36             { 37                 a[i][j]=getDis(x[i],y[i],x[j],y[j])*3.0/500; 38                 //printf("%d %d ==> %d %d\n",x[i],y[i],x[j],y[j]); 39             } 40         } 41     } 42 } 43 bool relax(int u,int v,double c) 44 { 45     if (dis[v]-dis[u]-c>1e-9) 46     { 47         dis[v]=dis[u]+c; 48         return true; 49     } 50     return false; 51 } 52 queue<int > q; 53 bool spfa(int src) 54 { 55     while (!q.empty()) q.pop(); 56     for (int i=1;i<=n;i++) 57     dis[i]=inf; 58     dis[src]=0; 59     memset(vis,0,sizeof(vis)); 60     q.push(src); 61     vis[src]=true; 62     while (!q.empty()) 63     { 64         int pre=q.front(); 65         q.pop(); 66         vis[pre]=false; 67         for (int i=1;i<=n;i++) 68         if (relax(pre,i,a[pre][i]) && !vis[i]) 69         { 70             vis[i]=true; 71             q.push(i); 72         } 73     } 74 } 75 int main() 76 { 77     scanf("%lf%lf%lf%lf",&x[1],&y[1],&x[2],&y[2]); 78     n=2; 79     double ca,cb; 80     int start,end; 81     int flag=0; 82     for (int i=1;i<imax_n;i++) 83     { 84         for (int j=1;j<imax_n;j++) 85         a[i][j]=0.0; 86     } 87     while (scanf("%lf%lf",&ca,&cb)!=EOF) 88     { 89         if (ca==-1 && cb==-1) 90         { 91             end=n; 92             for (int i=start;i<end;i++) 93             { 94                     a[i][i+1]=a[i+1][i]=getDis(x[i],y[i],x[i+1],y[i+1])*3.0/2000; 95                     //printf("%d %d ==> %d %d\n",x[i],y[i],x[j],y[j]); 96             } 97             flag=0; 98             continue; 99         }100         ++n;101         x[n]=ca;102         y[n]=cb;103         if (flag==0)104         {105             start=n;106             flag=1;107         }108     }109     init();110     spfa(1);111     printf("%.0f\n",dis[2]);112     return 0;113 }