POJ 1797 最短路

72 阅读 0 评论 48 点赞

我是靠谱客的博主感性舞蹈，最近开发中收集的这篇文章主要介绍POJ 1797 最短路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：

http://poj.org/problem?id=1797

题意：

给出N个城市M条边，每条边都有个容量，求一条运输路线，使城市1到城市N的运输量最大

代码：

31 int cost[MAXN][MAXN];
32 int d[MAXN];
33 int used[MAXN];
34 int n, m;
35
36 void dijkstra() {
37
memset(d, 0, sizeof(d));
38
memset(used, 0, sizeof(used));
39
d[0] = INF;
40
41
while (1) {
42
int v = -1;
43
rep(u, 0, n) if (!used[u] && (v == -1 || d[u] >= d[v])) v = u;
44
if (v == -1) break; used[v] = 1;
45
rep(u, 0, n) d[u] = max(d[u], min(d[v], cost[v][u]));
46 
}
47 }
48
49 int main() {
50
int T;
51
cin >> T;
52
rep(cas, 0, T) {
53
memset(cost, 0, sizeof(cost));
54
cin >> n >> m;
55
while (m--) {
56
int a, b, c;
57
scanf("%d%d%d", &a, &b, &c);
58
a--, b--;
59
cost[a][b] = cost[b][a] = c;
60 
}
61 
dijkstra();
62
cout << "Scenario #" << cas + 1 << ':' << endl;
63
cout << d[n - 1] << endl << endl;
64 
}
65
return 0;
66 }