Problem Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
Dijkstra:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int mx=1000000; 6 int n,m; 7 int v[105],ans[105]; 8 int map[105][105]; 9 void f(int x) 10 { 11 v[x]=1; 12 int i,p,mn; 13 for (i=1;i<=n;i++) ans[i]=map[x][i]; 14 while (1) 15 { 16 mn=mx; 17 p=x; 18 for (i=1;i<=n;i++) 19 { 20 if (!v[i]&&ans[i]<mn) 21 { 22 p=i; 23 mn=ans[i]; 24 } 25 } 26 if (p==x) return ; 27 v[p]=1; 28 for (i=1;i<=n;i++) 29 { 30 if (!v[i]&&ans[i]>ans[p]+map[p][i]) 31 ans[i]=ans[p]+map[p][i]; 32 } 33 } 34 } 35 int main() 36 { 37 int i,j,a,b,c; 38 while (~scanf("%d%d",&n,&m)) 39 { 40 if (n==0&&m==0) return 0; 41 for (i=1;i<=n;i++) 42 for (j=1;j<=n;j++) 43 { 44 if (i==j) map[i][j]=0; 45 else map[i][j]=mx; 46 } 47 while (m--) 48 { 49 scanf("%d%d%d",&a,&b,&c); 50 if (map[a][b]>c) 51 map[a][b]=map[b][a]=c; 52 } 53 memset(v,0,sizeof(v)); 54 f(1); 55 printf("%d ",ans[n]); 56 } 57 }
Dijkstra+优先队列：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 #include<queue> 6 using namespace std; 7 8 const int mx=105; 9 struct Node 10 { 11 int x,d; 12 Node(int a,int b){x=a;d=b;} 13 bool operator < (const Node & a) const 14 { 15 return d>a.d; 16 } 17 }; 18 vector<Node>g[mx]; 19 int ds[mx]; 20 int n,m; 21 22 void dijk() 23 { 24 priority_queue<Node>q; 25 q.push(Node(1,0)); 26 while (!q.empty()) 27 { 28 Node N=q.top();q.pop(); 29 for (int i=0;i<g[N.x].size();i++) 30 { 31 Node y=g[N.x][i]; 32 if (ds[y.x]>y.d+N.d) 33 { 34 ds[y.x]=y.d+N.d; 35 q.push(Node(y.x,ds[y.x])); 36 } 37 } 38 } 39 } 40 41 int main() 42 { 43 while (scanf("%d%d",&n,&m)&&n+m) 44 { 45 for (int i=1;i<=n;i++) 46 { 47 g[i].clear(); 48 ds[i]=1000000; 49 } 50 ds[1]=0; 51 int u,v,w; 52 while (m--) 53 { 54 scanf("%d%d%d",&u,&v,&w); 55 g[u].push_back(Node(v,w)); 56 g[v].push_back(Node(u,w)); 57 } 58 dijk(); 59 printf("%d ",ds[n]); 60 } 61 }
Floyd:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int main() 6 { 7 int n,m,i,j,k,a,b,c; 8 int map[108][108]; 9 while (~scanf("%d%d",&n,&m)) 10 { 11 if (n==0&&m==0) return 0; 12 for (i=1;i<=n;i++) 13 for (j=1;j<=n;j++) map[i][j]=10000000; 14 while (m--) 15 { 16 scanf("%d%d%d",&a,&b,&c); 17 map[a][b]=map[b][a]=c; 18 } 19 for (k=1;k<=n;k++) 20 for (i=1;i<=n;i++) 21 for (j=1;j<=n;j++) 22 if (map[i][j]>map[i][k]+map[k][j]) 23 map[i][j]=map[i][k]+map[k][j]; 24 printf("%d ",map[1][n]); 25 } 26 }
Dfs:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int n,m,a,b,c,t; 6 int map[108][108],v[108]; 7 void dfs(int x,int p) 8 { 9 if (p>t) return ; 10 if (x==n) 11 { 12 t=p; 13 return ; 14 } 15 int i; 16 for (i=2;i<=n;i++) 17 { 18 if (!v[i]&&map[x][i]) 19 { 20 v[i]=1; 21 dfs(i,p+map[x][i]); 22 v[i]=0; 23 } 24 } 25 } 26 int main() 27 { 28 int i,j; 29 while (~scanf("%d%d",&n,&m)) 30 { 31 if (n==0&&m==0) return 0; 32 memset(map,0,sizeof(map)); 33 memset(v,0,sizeof(v)); 34 while (m--) 35 { 36 scanf("%d%d%d",&a,&b,&c); 37 map[a][b]=map[b][a]=c; 38 } 39 t=1000000; 40 dfs(1,0); 41 printf("%d ",t); 42 } 43 }
Bellman_Ford
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; struct Eage { int u,v,w; }; Eage e[20005]; int cnt; int main() { while (~scanf("%d%d",&n,&m)&&n+m) { cnt=0; while (m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); e[cnt].u=a; e[cnt].v=b; e[cnt++].w=c; e[cnt].u=b; e[cnt].v=a; e[cnt++].w=c; } int d[105]; for (int i=2;i<=n;i++) d[i]=100000000; d[1]=0; for (int k=1;k<=n;k++) { for (int i=0;i<cnt;i++) { if (d[e[i].u]>d[e[i].v]+e[i].w) d[e[i].u]=d[e[i].v]+e[i].w; } } printf("%d ",d[n]); } }
spfa:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<queue> 6 #include<vector> 7 using namespace std; 8 9 const int mx=10004; 10 const int inf=1000000000; 11 struct Eage 12 { 13 int v,w,next; 14 }; 15 Eage eage[mx*2]; 16 int n,m,pos; 17 int head[mx]; 18 bool vs[mx]; 19 int d[mx]; 20 21 void init() 22 { 23 fill(head,head+n+1,-1); 24 fill(vs,vs+n+1,false); 25 fill(d,d+n+1,inf); 26 pos=0; 27 } 28 29 void add(int u,int v,int w) 30 { 31 eage[pos].v=v; 32 eage[pos].w=w; 33 eage[pos].next=head[u]; 34 head[u]=pos++; 35 } 36 37 void spfa() 38 { 39 queue<int>q; 40 d[1]=0; 41 q.push(1); 42 while (!q.empty()) 43 { 44 int u=q.front(); 45 q.pop(); 46 vs[u]=false; 47 for (int i=head[u];i!=-1;i=eage[i].next) 48 { 49 int v=eage[i].v; 50 int w=eage[i].w; 51 if (d[v]>d[u]+w) 52 { 53 d[v]=d[u]+w; 54 if (!vs[v]) 55 { 56 vs[v]=true; 57 q.push(v); 58 } 59 } 60 } 61 } 62 } 63 64 int main() 65 { 66 while (~scanf("%d%d",&n,&m)&&n+m) 67 { 68 init(); 69 while (m--) 70 { 71 int u,v,w; 72 scanf("%d%d%d",&u,&v,&w); 73 add(u,v,w); 74 add(v,u,w); 75 } 76 spfa(); 77 printf("%d ",d[n]); 78 } 79 }