POJ 2502 最短路

同一条地铁线上的站点相邻点间按照v2建边，然后所有点之间按照v1更新建边，所有的边都是双向边，both directions。

然后直接跑dij就好了，防止因为重复的站点多建了同样的点，把上限开到了500，AC。

一个小bug是因为数组开了500，然后初始化时访问了500导致越界，，，把其他位置的地址更改了检查了半天，衰，以后还是多开几十好点。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 #define inf 999999999
 8 double e[500][500];
 9 struct node
10 {
11     int x,y;
12 }P[500];
13 double dis(node A,node B)
14 {
15     double d1=(A.x-B.x)*(A.x-B.x),d2=(A.y-B.y)*(A.y-B.y);
16     return sqrt(d1+d2);
17 }
18 double dij(int N)
19 {
20  double d[505];
21  bool vis[505];
22  memset(vis,0,sizeof(vis));
23  for(int i=1;i<=N;++i) d[i]=inf;
24  d[1]=0;
25  for(int i=1;i<=N;++i)
26  {
27      int u;
28      double minv=inf;
29      for(int j=1;j<=N;++j) if(!vis[j]&&d[j]<minv) minv=d[u=j];
30      vis[u]=1;
31      for(int j=1;j<=N;++j)
32         if(!vis[j]&&d[j]>d[u]+e[u][j])
33         d[j]=d[u]+e[u][j];
34  }
35  return d[2];
36 }
37 int main()
38 {
39     freopen("in.txt","r",stdin);
40     int N,M,i,j,k;
41     double v1=10000.0/60;
42     double v2=40000.0/60;
43     while(cin>>P[1].x>>P[1].y>>P[2].x>>P[2].y){
44         int p=2,l=3,a,b;
45        for(i=1;i<500;++i)
46             for(j=1;j<500;++j)
47         e[i][j]=(i==j?0:inf);
48         while(cin>>a>>b){
49             if(a==-1&&b==-1) {l=p+1;continue;}
50             ++p;
51             P[p].x=a;
52             P[p].y=b;
53             if(p>l) e[p-1][p]=e[p][p-1]=min(e[p][p-1],dis(P[p],P[p-1])/v2);
54         }
55 
56 
57         for(i=1;i<=p;++i)
58             for(j=i+1;j<=p;++j)
59                  e[i][j]=e[j][i]=min(e[i][j],dis(P[i],P[j])/v1);
60         printf("%.0f
",dij(p));
61     }
62     return 0;
63 }