今天有点小偷懒了。。。 早上的时候就只敲了两个最短路径的题目，之所以说偷懒 。。 是因为之前就敲过了。。
好了 不说 废话 队友闲我啰嗦，先用了一个floyd 这个比较浪费时间的。。
不过之后写的djs就还行了。。。
不说了 直接看代码
View Code 1 #include<iostream> 2 #define min(a,b) a<b?a:b 3 #define INF 100000000 4 using namespace std; 5 int map[220][220]; 6 int main() 7 { 8 int m,n,s,e,w; 9 while(scanf("%d%d",&n,&m)!=EOF) 10 { 11 for(int i=0;i<n;i++) 12 { 13 for(int j=0;j<n;j++) 14 { 15 if(i==j)map[i][j]=0; 16 else 17 map[i][j]=INF; 18 } 19 } 20 for(int i=0;i<m;i++) 21 { 22 scanf("%d%d%d",&s,&e,&w); 23 if(w<map[s][e]) 24 { 25 map[s][e]=w; 26 map[e][s]=w; 27 } 28 } 29 scanf("%d%d",&s,&e); 30 for(int i=0;i<n;i++) 31 for(int j=0;j<n;j++) 32 for(int k=0;k<n;k++) 33 { 34 map[j][k]=min(map[j][k],map[j][i]+map[i][k]); 35 } 36 if(map[s][e]<INF) 37 printf("%d\n",map[s][e]); 38 else 39 printf("-1\n"); 40 } 41 return 0; 42 } 43 44 Djs 45 #include<iostream> 46 #define min(a,b) a<b?a:b 47 #define INF 10000000 48 using namespace std; 49 int map[202][202]; 50 int q[200]; 51 int main() 52 { 53 int n,m,s,e,w,head,tail; 54 while(scanf("%d%d",&n,&m)!=EOF) 55 { 56 for(int i=0;i<n;i++) 57 { 58 for(int j=0;j<n;j++) 59 { 60 if(i==j)map[i][j]=0; 61 else 62 map[i][j]=INF; 63 } 64 } 65 head=tail=0; 66 for(int i=0;i<m;i++) 67 { 68 scanf("%d%d%d",&s,&e,&w); 69 map[e][s]=map[s][e]=min(map[s][e],w); 70 } 71 scanf("%d%d",&s,&e); 72 for(int i=0;i<n;i++) 73 { 74 if(map[s][i]<INF&&s!=i){q[tail++]=i;} 75 } 76 visit[s]=1; 77 while(head<tail) 78 { 79 for(int i=0;i<n;i++) 80 { 81 if(map[s][q[head]]+map[q[head]][i]<map[s][i]) 82 { 83 map[s][i]=map[s][q[head]]+map[q[head]][i]; 84 q[tail++]=i; 85 } 86 } 87 head++; 88 } 89 if(map[s][e]<INF) 90 printf("%d\n",map[s][e]); 91 else 92 printf("-1\n"); 93 } 94 return 0; 95 }
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667114.html
相关资源：JAVA上百实例源码以及开源项目