kuangbin专题专题四 Heavy Transportation POJ

题目链接：https://vjudge.net/problem/POJ-1797

思路：请参考我列出的另一个题目，和这个题目要求的值相反，另一个清楚后，这个写的解释就明白了。

另一个类似题目的博客：https://www.cnblogs.com/SSummerZzz/p/11200821.html

其实，我们要求的就是从起始点开始到结束点的所有路线中每条路线都选出个子最短的两点通路距离，然后从这些最短通路中选出最长的那条，即最大的最小距离。

那就是way[ x ] 里面存的变成了从起始点到这个点的所有路线的最大的最短通路距离，然后让这个值尽可能的大，即最大化最小距离。

（代码不写注释了，懂了代码就很好理解，注意一下init()函数中，初始化距离变成了0，不清楚的话可以自己思考）

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <string>
 6 #include <cmath>
 7 #include <iomanip>
 8 using namespace std;
 9 
10 typedef long long LL;
11 #define inf (1LL << 30) - 1
12 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
13 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
14 #define per(i,j,k) for(int i = (j); i >= (k); i--)
15 #define per__(i,j,k) for(int i = (j); i > (k); i--)
16 
17 const int N = 1010;
18 int mp[N][N];
19 bool vis[N];
20 int w[N];
21 int n,m;
22 
23 void init(){
24 
25     rep(i,1,n) vis[i] = false;
26     rep(i,1,n) rep(j,1,n) {
27         mp[i][j] = 0;
28     }
29 }
30 
31 void input(){
32 
33     int u,v,W;
34     rep(i,1,m){
35         cin >> u >> v >> W;
36         if(mp[u][v] < W) mp[u][v] = mp[v][u] = W;
37     } 
38 }
39 
40 void dijkstra(){
41 
42     rep(i,1,n) w[i] = mp[1][i];
43     vis[1] = true;
44     
45     rep(i,2,n){
46         
47         int x = -1;
48         int W = -1;
49 
50         rep(j,1,n){
51             if(!vis[j] && W < w[j]) W = w[x = j];
52         }
53 
54         if(x == -1) continue;
55 
56         vis[x] = true;
57         rep(k,1,n){
58             if(!vis[k] && w[k] < min(w[x], mp[x][k])){
59                 w[k] = min(w[x], mp[x][k]);
60             }
61         }
62     }
63 }
64 
65 int main(){
66 
67 
68     ios::sync_with_stdio(false);
69     cin.tie(0);
70 
71     int T;
72     cin >> T;
73     rep(i,1,T){
74 
75         cin >> n >> m;
76 
77         init();
78         input();
79         dijkstra();
80 
81         cout << "Scenario #" << i << ":" << endl;
82         cout << w[n] << endl << endl;
83     }
84 
85     getchar();getchar();
86 
87     return 0;
88 }