1205. By the Underground or by Foot?(ｓｐｆａ）

简单题　有一些小细节　两个站可能不相连　但是可以走过去
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<queue>
  8 #include<cmath>
  9 using namespace std;
 10 #define INF 0xfffffff
 11 vector<int>ed[310];
 12 double v1,v2,x[310],y[310],w[210][210],dis[210];
 13 int n,vis[210],pa[210],o[210];
 14 void spfa(int s,int e)
 15 {
 16     int i;
 17     for(i =0 ; i <= n ; i++)
 18     dis[i] = INF;
 19     dis[s] = 0;
 20     queue<int>q;
 21     vis[s] = 1;
 22     q.push(s);
 23     while(!q.empty())
 24     {
 25         int u  = q.front();
 26         q.pop();
 27         vis[u] = 0;
 28         for(i = 0 ; i < (int)ed[u].size() ; i++)
 29         {
 30             int v = ed[u][i];
 31             if(dis[v]>dis[u]+w[u][v])
 32             {
 33                 pa[v] = u;
 34                 dis[v] = dis[u]+w[u][v];
 35                 if(!vis[v])
 36                 {
 37                     vis[v] = 1;
 38                     q.push(v);
 39                 }
 40             }
 41         }
 42     }
 43     printf("%.7lf
",dis[e]);
 44     int g = 0,x=e;
 45     while(pa[x]!=s)
 46     {
 47         x = pa[x];
 48         g++;
 49         o[g] = x;
 50     }
 51     printf("%d",g);
 52     for(i = g ; i>=1 ; i--)
 53     printf(" %d",o[i]);
 54     puts("");
 55 }
 56 double dist(int u,int v)
 57 {
 58     double s = sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));
 59     return s;
 60 }
 61 int main()
 62 {
 63     int i,j,u,v;
 64     cin>>v1>>v2;
 65     cin>>n;
 66     for(i = 1; i <= n ;i++)
 67     {
 68         scanf("%lf%lf",&x[i],&y[i]);
 69     }
 70     for(i = 0 ;i <= n+1 ; i++)
 71         for(j = 0  ; j <= n+1 ; j++)
 72         w[i][j] = INF;
 73     while(scanf("%d%d",&u,&v)!=EOF)
 74     {
 75         if(!u&&!v)
 76         break;
 77         w[u][v] = dist(u,v)/v2;
 78         w[v][u] = w[u][v];
 79         ed[u].push_back(v);
 80         ed[v].push_back(u);
 81     }
 82     for(i = 1; i <= n ; i++)
 83         for(j = i+1 ;j <= n ;j++)
 84         {
 85             if(w[i][j]==INF)
 86             {
 87                 w[i][j] = dist(i,j)/v1;
 88                 w[j][i] = w[i][j]/v1;
 89                 ed[i].push_back(j);
 90                 ed[j].push_back(i);
 91             }
 92         }
 93     scanf("%lf%lf%lf%lf",&x[0],&y[0],&x[n+1],&y[n+1]);
 94     for(i = 1; i <= n+1 ;i++)
 95     {
 96         w[0][i] = dist(i,0)/v1;
 97         w[i][0] = w[0][i];
 98         ed[0].push_back(i);
 99         ed[i].push_back(0);
100         w[n+1][i] = dist(i,n+1)/v1;
101         w[i][n+1] = w[n+1][i];
102         ed[i].push_back(n+1);
103         ed[n+1].push_back(i);
104     }
105     n++;
106     for(i = 0; i <= n ;i++)
107     w[i][i] = 0;
108     spfa(0,n);
109     return 0;
110 }
View Code