首页 > 代码库 > poj1797 - Heavy Transportation(最大边,最短路变形spfa)
poj1797 - Heavy Transportation(最大边,最短路变形spfa)
题目大意：
给你以T， 代表T组测试数据，一个n代表有n个点， 一个m代表有m条边， 每条边有三个参数，a,b,c表示从a到b的这条路上最大的承受重量是c，
让你找出一条线路，要求这条线路上的最大的承重， 在所有其他线路最小。
题目分析：
这里只要将spfa进行一下变形就可以解决这问题了。
首先 我们的dist数组，起点位置要初始化为 INF， 其他位置初始化为 0
然后我们更新 dist 数组， 结果输出 dist[n]就行了
为什么这样写： 因为我们每次要找 所有路径中的最大边的最小一个， 说的可能有写绕口
递推式是： dist[e] = min(dist[e], max(dist[s], G[s][i]) );
下面是代码：
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 #define INF 0xfffffff 9 #define maxn 105010 11 struct Edge12 {13 int e;14 long long w;15 };16 vector<Edge> G[maxn];17 long long dist[maxn];18 bool vis[maxn];19 int m, n;20 long long Spfa()21 {22 Edge P, Pn;23 P.e = 1, P.w = 0;24 queue <Edge> Q;25 Q.push(P);26 27 while( !Q.empty() )28 {29 P = Q.front();30 Q.pop();31 vis[P.e] = false;32 int len = G[P.e].size();33 34 for(int i=0; i<len; i++)35 {36 Pn = G[P.e][i];37 38 if(dist[Pn.e] < min(dist[P.e],Pn.w) )39 {40 dist[Pn.e] = min(dist[P.e],Pn.w);41 42 if(!vis[Pn.e])43 {44 vis[Pn.e] = true;45 Q.push(Pn);46 }47 }48 }49 }50 return dist[n];51 }52 void Init()53 {54 for(int i=1; i<=n ;i++)55 {56 G[i].clear();57 vis[i] = false;58 dist[i] = 0;59 }60 dist[1] = INF;61 }62 int main()63 {64 int T, cas = 1;65 Edge P;66 cin >> T;67 68 while(T--)69 {70 scanf("%d%d",&n,&m);71 72 Init();73 for(int i=0; i<m; i++)74 {75 int a, b, c;76 scanf("%d%d%d",&a,&b,&c);77 P.e = b, P.w = c;78 79 G[a].push_back(P);80 81 P.e = a;82 83 G[b].push_back(P);84 }85 long long ans = Spfa();86 87 printf("Scenario #%d:\n%lld\n",cas++,ans);88 if(T)89 printf("\n");90 91 }92 return 0;93 }
poj1797 - Heavy Transportation(最大边,最短路变形spfa)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。