本文主要是介绍zoj 1952 poj 2263 Heavy Cargo，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：在一个无向图中，给你起点和终点求出这两点之间一条路径，该路径要求其中最小的边最大。
思路：用spfa的思想，用dist[i]表示从起点除法到点i的最大值（该路径中的最小的边）,然后不断松弛更新dist[i],当不能在松弛时说明所有结果已经得出。
因为我们使用dist[i]表示的当前路径中的最小权值，所以松弛时我们要取min(dist[u],edge[u][v]),取两者中的较小值，然后和dist[v]比较，若min(dist[u],edge[u][v])>dist[v]，则说明发现一条更好的路径。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>using namespace std;const int inf = 100000000;
const int maxn = 205;struct node{int v;int w;node(int _v, int _w){v = _v; w = _w;}
};int n,m;
map<string,int> Map;
vector<node> list[maxn];
int s,t;//起点、终点
int dist[maxn];
bool inq[maxn];bool input(){string u,v;int w;int cnt = 1;cin>>n>>m;if(n+m == 0) return false;//清零for(int i = 0; i <= n; i++) list[i].clear();Map.clear(); for(int i = 0; i < m; i++){cin>>u>>v;cin>>w;if(Map[u] == 0) Map[u] = cnt++;if(Map[v] == 0) Map[v] = cnt++;list[Map[u]].push_back(node(Map[v],w));list[Map[v]].push_back(node(Map[u],w));}string a,b;cin>>a>>b;s = Map[a];t = Map[b]; return true;
}void spfa(){queue<int> q;for(int i = 0; i <= n; i++){dist[i] = -inf;inq[i] = false;}dist[s] = inf;q.push(s);inq[s] = true;while(!q.empty()){int u = q.front(); q.pop(); inq[u] = false;for(int i = 0; i < list[u].size(); i++){int v = list[u][i].v;int w = min(dist[u],list[u][i].w);//取上个城市和扩展边之间的最小值 if(w > dist[v]){//发现载重更大的路径 dist[v] = w;if(!inq[v]){q.push(v);inq[v] = true;}}}}
}void solve(){static int cnt = 0;spfa();printf("Scenario #%d\n",++cnt);printf("%d tons\n",dist[t]);puts("");
}int main(){ while(input()){solve();}return 0;
}这篇关于zoj 1952 poj 2263 Heavy Cargo的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
