POJ 1797 (最短路变形)

题目大意：有n个城市，m条道路，在每条道路上有一个承载量，现在要求从1到n城市最大承载量，而最大承载量就是从城市1到城市n所有通路上的最大承载量

解题思路：相当于让选择的那条路最小值尽量大,更改一下最短路即可

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define LL long long
#define INF 0x3f3f3f3f
#define maxn 1024
#define Pair pair<int, int>
using namespace std;
struct edge
{
int to, cost;
};
int V;
int Test, m, test;
vector<edge> G[maxn];
int d[maxn];
bool operator<(const Pair &a, const Pair &b)
{
return a.first < b.first;
}
void dijkstra(int s)
{
priority_queue<Pair> que;
fill (d, d + V + 2, 0);
d[s] = INF;
int as = INF;
que.push(Pair(INF, s));
while (!que.empty()) {
Pair p = que.top();
que.pop();
int v = p.second;
if(v == V) break;
if (d[v] > p.first) continue;
for (int i = 0; i < G[v].size(); ++i) {
edge e = G[v][i];
if(d[e.to] < min(d[v], e.cost)) {
d[e.to] = min(d[v], e.cost);
que.push(Pair(d[e.to], e.to));
}
}
}
printf("Scenario #%d:n", test);
printf("%dnn", d[V]);
}
int main()
{
scanf("%d", &Test);
test = 0;
while (test != Test) {
test++;
scanf("%d%d", &V, &m);
for(int i = 0; i <= V; ++i)
G[i].clear();
int from, to, cost;
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &from, &to, &cost);
edge demo;
demo.to = to;
demo.cost = cost;
G[from].push_back(demo);
demo.to = from;
G[to].push_back(demo);
}
dijkstra(1);
}
return 0;
}

最后

以上就是活力舞蹈为你收集整理的POJ 1797 (最短路变形)的全部内容，希望文章能够帮你解决POJ 1797 (最短路变形)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。