HDU 2066 一个人的旅行. - c++编程基础

Problem Description 虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
Input 输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。
Output 输出草儿能去某个喜欢的城市的最短时间。
Sample Input

Sample Output

Author Grass ==== 最短路径，题目说的很清楚，注意重边的情况。一开始的思路。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int INF=0x3f3f3f3f; const int N=1000+10; int S,T,D,n; int e[N][N],d[N],v[N]; int ss[N],dd[N]; void Dijkstra() { memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); for(int i=0;i<=S;i++) //思路是令多个起点的初始路径为0 d[ss[i]]=0; for(int i=1;i<=n;i++) { int m=INF,x; for(int y=1;y<=n;y++) if(!v[y]&&d[y]<=m) m=d[x=y]; v[x]=1; for(int y=1;y<=n;y++) if(d[y]>d[x]+e[x][y]) d[y]=d[x]+e[x][y]; } } int main() { while(scanf("%d%d%d",&T,&S,&D)==3) { memset(e,0x3f,sizeof(e)); n=0; for(int i=1;i<=T;i++) { int p,q,w; scanf("%d%d%d",&p,&q,&w); if(e[q][p]>w) e[p][q]=e[q][p]=w; n=max(n,p); n=max(n,q); } for(int i=1;i<=S;i++) scanf("%d",&ss[i]); for(int i=1;i<=D;i++) scanf("%d",&dd[i]); int m=INF; for(int j=1;j<=D;j++) { Dijkstra(); if(d[dd[j]]
      
       
 调用了D次Dijkstra，跑得很慢。 
       
 ==== 其实可以是以家乡为起点，再跟多个邻近的城市相连，边的权值设为0就行，这样就只用调用一次Dijkstra，快多了。 
       #include
        
         
#include
         
           #include
          
            #include
           
             using namespace std; const int INF=0x3f3f3f3f; const int N=1000+10; int S,T,D,n; int e[N][N],d[N],v[N]; int ss[N],dd[N]; int Dijkstra() { memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); d[0]=0; for(int i=0;i<=n;i++) { int m=INF,x; for(int y=0;y<=n;y++) if(!v[y]&&d[y]<=m) m=d[x=y]; v[x]=1; for(int y=0;y<=n;y++) if(d[y]>d[x]+e[x][y]) d[y]=d[x]+e[x][y]; } } int main() { while(scanf("%d%d%d",&T,&S,&D)==3) { memset(e,0x3f,sizeof(e)); n=0; int i; for(i=1;i<=T;i++) { int p,q,w; scanf("%d%d%d",&p,&q,&w); if(e[q][p]>w) e[p][q]=e[q][p]=w; n=max(n,p); n=max(n,q); } for(i=1;i<=S;i++) { scanf("%d",&ss[i]); e[0][ss[i]]=e[ss[i]][0]=0; //再与领近的城市连一条权值为0的路 } for(int i=1;i<=D;i++) scanf("%d",&dd[i]); int m=INF,ans; Dijkstra(); for(int j=1;j<=D;j++) { ans=d[dd[j]]; if(ans