题目链接：http://poj.org/problem?id=2263
问题描述：给定一个无向图，每条边有一个最大载重量。求从起点到终点的最大载重路径。
#include #include #include #include #include #define N 202 using namespace std; int gra[N][N], dis[N], vis[N], n; void dijkstra(int beg, int end) { int i, j, k, temp, m; for (i = 1; i <= n; i++) { dis[i] = gra[beg][i]; vis[i] = false; } vis[beg] = true; for (i = 2; i <= n; i++) { k = 0; temp = 0; for (j = 1; j <= n; j++) { if (!vis[j] && dis[j] > temp) { temp = dis[j]; k = j; } } if (k == end) { printf("%d tons\n", temp); return; } vis[k] = true; for (j = 1; j <= n; j++) { if (!vis[j]) { m = min(temp, gra[k][j]); if (m > dis[j]) dis[j] = m; } } } } int main() { int i, j, k, m, h, count = 1; string s1, s2; map mp; while (scanf("%d%d", &n, &m), n || m) { k = 1; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) gra[i][j] = 0; while (m--) { cin >> s1 >> s2 >> h; if (mp.find(s1) == mp.end()) mp[s1] = k++; if (mp.find(s2) == mp.end()) mp[s2] = k++; i = mp[s1]; j = mp[s2]; if (h > gra[i][j]) gra[i][j] = gra[j][i] = h; } cin >> s1 >> s2; printf("Scenario #%d\n", count++); dijkstra(mp[s1], mp[s2]); printf("\n"); } return 0; }
参考链接：https://www.cnblogs.com/YogurtShen/archive/2012/08/30/2664306.html
京公网安备 11010802041100号