hdu 2680 Choose the best route 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2680
题目意思：实质就是给定一个多源点到单一终点的最短路。
卑鄙题～～～有向图。初始化map时 千万不要写成 map[i][j] = map[j][i] = X。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 #define INF 0xfffffff 8 const int maxn = 1000 + 5; 9 int dist[maxn], map[maxn][maxn], vis[maxn]; 10 int n, m, s; 11 12 void Init() 13 { 14 for (int i = 0; i <= n; i++) 15 { 16 for (int j = 0; j <= n; j++) 17 map[i][j] = (i == j ? 0 : INF); 18 } 19 int p, q, t, w; 20 for (int i = 0; i < m; i++) 21 { 22 scanf("%d%d%d", &p, &q, &t); 23 if (map[p][q] > t) 24 map[p][q] = t; // 写成map[p][q] = map[q][p] = t 会wa的！！！ 25 } 26 scanf("%d", &w); 27 for (int i = 0; i < w; i++) 28 { 29 scanf("%d", &p); 30 map[0][p] = map[p][0] = 0; 31 } 32 for (int i = 0; i <= n; i++) 33 dist[i] = map[0][i]; 34 } 35 36 void Dijkstra() 37 { 38 int u, maxx; 39 memset(vis, 0, sizeof(vis)); 40 for (int i = 0; i <= n; i++) 41 { 42 maxx = INF; 43 for (int j = 0; j <= n; j++) 44 { 45 if (!vis[j] && dist[j] < maxx) 46 maxx = dist[u=j]; 47 } 48 vis[u] = 1; 49 for (int j = 0; j <= n; j++) 50 { 51 if (dist[j] > dist[u] + map[u][j]) 52 dist[j] = dist[u] + map[u][j]; 53 } 54 } 55 } 56 57 int main() 58 { 59 while (scanf("%d%d%d", &n, &m, &s) != EOF) 60 { 61 Init(); 62 Dijkstra(); 63 printf("%d ", dist[s] == INF ? -1 : dist[s]); 64 } 65 return 0; 66 }