hdu 1874 畅通工程续
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1874
题目大意：计算出要从起点到终点，最短需要行走多少距离。
提供两种方法，第一种：dijkstra算法，很快的找到最小距离值；第二种：floyd算法，三个for循环，很容易超时，注意细节~
代码一：dijkstra算法
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 int main () 7 { 8 int a,b,c,n,m,l,k; 9 const int INF=10000; 10 int map[205][205],r[205]; 11 int vis[205]; 12 while (cin>>n>>m) 13 { 14 memset(vis,0,sizeof(vis)); 15 for (int i=0; i<n; i++) 16 for (int j=0; j<n; j++) 17 { 18 if (i!=j) 19 map[i][j]=INF; 20 else 21 map[i][j]=0; 22 } 23 while (m--) 24 { 25 cin>>a>>b>>c; 26 if (map[a][b]>c) 27 map[a][b]=map[b][a]=c; 28 } 29 cin>>a>>b; 30 for (int i=0; i<n; i++) 31 { 32 r[i]=map[a][i]; 33 vis[i]=0; 34 } 35 for (int i=1; i<n; i++) 36 { 37 l=INF; 38 k=0; 39 for (int j=0; j<n; j++) 40 { 41 if (vis[j]==0&&r[j]<l) 42 { 43 l=r[j]; 44 k=j; 45 } 46 } 47 vis[k]=1; 48 for (int j=0; j<n; j++) 49 { 50 if (!vis[j]&&r[j]>r[k]+map[k][j]) 51 r[j]=r[k]+map[k][j]; 52 } 53 54 } 55 //cin>>a>>b; 56 if (r[b]<INF) 57 printf ("%d ",r[b]); 58 else 59 printf ("-1 "); 60 } 61 return 0; 62 }
代码二：floyd算法
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define INF 10000 5 const int maxn = 201; 6 int r[maxn][maxn]; 7 8 int main () 9 { 10 int n,m; 11 while (scanf("%d%d",&n,&m)!=EOF) 12 { 13 memset(r,INF,sizeof(r)); 14 int a,b,c; 15 while (m--) 16 { 17 scanf("%d%d%d",&a,&b,&c); 18 if (r[a][b]>c) 19 { 20 r[a][b]=r[b][a]=c; 21 } 22 } 23 for (int i=0; i<n; i++) 24 r[i][i]=0; 25 for (int k=0; k<n; k++) 26 for (int i=0; i<n; i++) 27 for (int j=0; j<n; j++) 28 { 29 if (r[i][j]>r[i][k]+r[k][j]) 30 { 31 r[i][j]=r[j][i]=r[i][k]+r[k][j]; 32 } 33 } 34 scanf("%d%d",&a,&b); 35 if (r[a][b]<INF) 36 printf ("%d ",r[a][b]); 37 else 38 printf ("-1 "); 39 } 40 return 0; 41 }