首页 > 代码库 > POJ 1797 最短路
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 }
POJ 1797 最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。