poj 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("%d\n\n",SPFA());
59     }
60     return 0;
61 }
62 
63 
64

View Code

秒客网

poj 1797(最短路变形)

相关文章