POJ - 1797 传送门
Description
Background
Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.
Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.
Problem
You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo’s place) to crossing n (the customer’s place). You may assume that there is at least one path. All streets can be travelled in both directions.
Input
The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.
Output
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line.
Sample Input
1
3 3
1 2 3
1 3 4
2 3 5
Sample Output
Scenario #1:
4
题目大意
给我们 n 个点，以及两个点之间的路的承重，我们要求的就是在
多条完整通路中的单条路的最小承重中选取一个最大值
分析样例如下：
1 - 2的承重是3
1 - 3的承重是4
2 - 3的承重是5
因此 1 - n 有两条路：
First： 1 - 2 - 3
Second：1 - 3
对于第一条路完整通路中单条路的最小承重是 3 ，而第二条路直接连向终点所以最小承重是 4
我们从这两个最小承重3 和 4选取一个最大值就是4
解题思路
根据题意求
多个最小值的最大值去修改 Dijkstra 的松弛操作，当最大承重和与其相连的的边的最小值比暂时最大承重dis[k]大，说明此时可以更新让暂时最大承重更大，依此类推，到最后得到的承重是最大的，由于 Folyd 是O（n3）的，还是选择 Dijkstra 吧
ps：在给 Folyd 交了发 TLE 之后果断选择了O（n2）的Dijkstra
AC代码
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1e3+9;
const int inf = 0x3f3f3f;
int n,m;
int map[maxn][maxn];
int from ,to , val;
int dis[maxn];
int vis[maxn];
void Folyd()//Folyd 时间复杂度是 O（n?）--> TLE
{for(int k = 1 ; k <= n ; k++){for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= n ; j++){if(i != j && j != k && k != i){if(min(map[i][k], map[k][j]) >= map[i][j])//本次 i - j 中的最小承重若大于原先 i - j 的最大承重就更新 i - j 的最大承重{map[i][j] = max(min(map[i][k] ,map[k][j]),map[i][j]);//max()显得有些多余,因为上面已经判断过}}}}}
}
void Dijkstra()//Dijkstra 时间复杂度是 O（n?）--> AC
{for(int i = 1 ; i <= n ; i++){dis[i] = map[1][i];}vis[1] = 1;dis[1] = 0;for(int i = 2; i <= n; i++){int maxn = -inf;int pos = 0;for(int j = 1 ; j <= n ; j++){if(vis[j] == -1 && dis[j] > maxn){maxn = dis[j];//（暂时最大承重）因为要求的是最大承重所以这里找最大承重pos = j;}}vis[pos] = 1;for(int k = 1; k <= n ; k++)//改变松弛操作{if(vis[k] == -1 && dis[k] < min(maxn,map[pos][k]))//最大承重和与其相连的的边的最小值如果比暂时最大承重dis[k]大，说明此时可以更新让暂时最大承重更大{dis[k] = min(maxn,map[pos][k]);}}}
}
int main()
{int t;scanf("%d",&t);while(t--){ static int count = 0;memset(vis,-1,sizeof(vis));memset(map,0,sizeof(map));//map这里要初始化,因为没初始化WA掉好几发找不到原因,之前没初始化map也没事,吸取这次教训scanf("%d %d",&n,&m);for(int i = 1 ; i <= m ; i++){scanf("%d %d %d",&from,&to,&val);map[from][to] = map[to][from] = val;}
// Folyd();count++;Dijkstra();count++;printf("Scenario #%d:\n",count);
// printf("%d\n\n",map[1][n]);printf("%d\n\n",dis[n]);}return 0;
}