这道题用djs算法就可以的。。。起初用FLOYD算法结果超时了。。。用djs时memset函数没用好。。。
结果输出都是错的。。定义数组初始最大时要这样定义
#define MAX 0x4f4f4f4f
int map【1001】【1001】;
memset(map,0x4f,sizeof(map));
还有就是把终点作为起始点
代码:
View Code
1 #include<iostream> 2 #define MAX 0x4f4f4f4f 3 using namespace std; 4 int map[1002][1002]; 5 int dis[1002]; 6 int n,m,mudi,hash[1002]; 7 void djs(int v) 8 { 9 int i,j,index; 10 int mi; 11 for(i=1;i<=n;i++) 12 { 13 dis[i]=map[v][i]; 14 hash[i]=0; 15 } 16 dis[v]=0; 17 hash[v]=1; 18 for(i=1;i<=n;i++) 19 { 20 mi=MAX; 21 index = 0; 22 for(j=1;j<=n;j++) 23 { 24 if(!hash[j]&&dis[j]<mi) 25 { 26 index=j; 27 mi=dis[j]; 28 } 29 } 30 hash[index]=1; 31 for(j=1;j<=n;j++) 32 { 33 if(!hash[j]&&dis[j]>dis[index]+map[index][j]) 34 dis[j]= dis[index]+map[index][j]; 35 } 36 } 37 } 38 int main() 39 { 40 int w,im; 41 int x,y,t; 42 int i,j; 43 while(cin>>n>>m>>mudi) 44 { 45 memset(map,0x4f,sizeof(map)); 46 47 for(i=1;i<=m;i++) 48 { 49 cin>>x>>y>>t; 50 if(t<map[y][x]) 51 map[y][x]=t; 52 } 53 djs(mudi); 54 cin>>w; 55 im=MAX; 56 while(w--) 57 { 58 cin>>x; 59 if(dis[x]<im) 60 im=dis[x]; 61 } 62 if(im<MAX) 63 cout<<im<<endl; 64 else 65 cout<<-1<<endl; 66 } 67 return 0; 68 }