poj 1797(最短路变形)

50 阅读 0 评论 33 点赞

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

概述

题目链接：http://poj.org/problem?id=1797

思路：题目意思很简单，n个顶点，m条路，每条路上都有最大载重限制，问1->n最大载重量。其实就是一最短路的变形，定义weight[i]表示源点到顶点i的最大载重量，初始化为0,之后不断去更新就行了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 #define MAXN 1010
 9 #define inf 1<<30
10
11 struct Edge{
12
int v,w;
13
Edge(int vv,int ww):v(vv),w(ww){}
14 };
15 int weight[MAXN];//源点到各点的最大载重量
16 bool mark[MAXN];
17 int n,m;
18
19 vector<vector<Edge> >map;
20
21 int SPFA()
22 {
23
memset(mark,false,(n+2)*sizeof(bool));
24
for(int i=1;i<=n;i++)weight[i]=0;
25
weight[1]=inf;
26
queue<int>Q;
27
Q.push(1);
28
while(!Q.empty()){
29
int u=Q.front();
30 
Q.pop();
31
mark[u]=false;
32
for(int i=0;i<map[u].size();i++){
33
int v=map[u][i].v,w=map[u][i].w;
34
int ww=min(weight[u],w);
35
if(ww>weight[v]){
36
weight[v]=ww;
37
if(!mark[v]){ mark[v]=true;Q.push(v); }
38 
}
39 
}
40 
}
41
return weight[n];
42 }
43
44
45 int main()
46 {
47
int _case,u,v,w,t=1;
48
scanf("%d",&_case);
49
while(_case--){
50
scanf("%d%d",&n,&m);
51
map.clear();map.resize(n+2);
52
while(m--){
53
scanf("%d%d%d",&u,&v,&w);
54 
map[u].push_back(Edge(v,w));
55 
map[v].push_back(Edge(u,w));
56 
}
57
printf("Scenario #%d:n",t++);
58
printf("%dnn",SPFA());
59 
}
60
return 0;
61 }
62
63
64