最短路 HDU


Dijkstra解法：

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <sstream>
 7 
 8 #define INF 1000000000
 9 
10 using namespace std;
11 int N, M;
12 int dist[101],g[101][101];
13 int vis[101];
14 
15 
16 void dijkstra(int start)
17 {
18     for(int i = 1; i <= N; ++i)
19     {
20         dist[i] = g[start][i];
21         vis[i] = 0;
22     }
23     vis[start] = 1; 
24     
25     while(1)
26     {
27         int mark = -1, minDist = INF;
28         for(int i = 1; i <= N; ++i)
29         {
30             if(!vis[i] && dist[i] < minDist)
31             {
32                 minDist = dist[i];
33                 mark = i;
34             }
35         }
36         
37         if(mark == -1)        // 找不到未收录的节点，则说明算法结束，退出 
38             break;
39             
40         vis[mark] = 1;
41         
42         for(int i = 1; i <= N; ++i)
43         {
44             if(!vis[i])
45                 dist[i] = min(dist[i], dist[mark] + g[mark][i]);
46         }
47     }
48 }
49 
50 int main()
51 {
52     while(cin >> N >> M)
53     {
54         if(N == 0 && M == 0)
55             break;
56 
57         for(int i = 1; i <= N; ++i)
58             for(int j = 1; j <= N; ++j)
59             {
60                 if(i == j)
61                     g[i][j] = 0;
62                 else
63                     g[i][j] = INF;
64             }
65 
66         for(int i = 1; i <= M; ++i)
67         {
68             int a,b,c;
69             cin >> a >> b >> c;
70             g[a][b] = g[b][a] = c;
71         }
72 
73         dijkstra(1);
74         cout << dist[N] << endl;
75 
76     }
77 
78     return 0;
79 }

Floyd解法:

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <sstream>
 7 
 8 using namespace std;
 9 
10 int dis[101][101];
11 
12 int main()
13 {
14        int N, M;
15     while(cin >> N >> M)
16     {
17         if(N == 0 && M == 0)
18             break;
19         
20         for(int i = 1; i <= N; ++i)
21         {
22             for(int j = 1; j <= N; ++j)
23             {
24                 if(i == j)
25                     dis[i][j] = 0;
26                 else
27                     dis[i][j] = 1100000; 
28             }
29         }
30         
31         int a, b, c;
32         for(int i = 1; i <= M; ++i)
33         {
34             cin >> a >> b >> c;
35             if(dis[a][b] > c)
36                 dis[a][b] = dis[b][a] = c;
37             
38         }
39         
40         for(int k = 1; k <= N; ++k)
41             for(int i = 1; i <= N; ++i)
42                 for(int j = 1; j <= N; ++j)
43                 {
44                     if(dis[i][j] > dis[i][k] + dis[k][j])
45                         dis[i][j] = dis[i][k] + dis[k][j];
46                 }
47                 
48         cout << dis[1][N] << endl;
49     } 
50        
51        
52        
53        
54     return 0;
55 }