题意
给你n个点，1为起点，n为终点，要求所有1到n所有路径中每条路径上最小值的最最值。
思路
不想打最短路
跑一边最大生成树，再扫一遍1到n的路径，取最小值即可，类似Frogger POJ - 2253，代码都没怎么改
常数巨大的丑陋代码
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <math.h>
# include <algorithm>
using namespace std;
# define IL inline
# define RG register
# define UN unsigned
# define ll long long
# define rep(i, a, b) for(RG int i = a; i <= b; i++)
# define per(i, a, b) for(RG int i = b; i >= a; i--)
# define uev(e, u) for(RG int e = ft[u]; e != -1; e = edge[e].nt)
# define mem(a, b) memset(a, b, sizeof(a))
# define max(a, b) (((a) > (b)) ? (a) : (b))
# define min(a, b) (((a) < (b)) ? (a) : (b))
# define Swap(a, b) a ^= b, b ^= a, a ^= b;
IL ll Get(){
RG char c = '!'; RG ll x = 0, z = 1;
while(c != '-' && (c < '0' || c > '9')) c = getchar();
if(c == '-') z = -1, c = getchar();
while(c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
return x*z;
}
const int MAXN = 1000001;
int ft[MAXN], n, cnt, vis[MAXN], fa[MAXN], m, ans = 2147483647;
struct Edge{
int to, nt, f;
} edge[MAXN<<1];
struct _Edge{
int u, v, f;
IL bool operator < (_Edge b) const{
return f > b.f;
}
} _edge[MAXN];
IL void Add(RG int u, RG int v, RG int f){
edge[cnt] = (Edge){v, ft[u], f}; ft[u] = cnt++;
}
IL int Find(RG int x){
return fa[x] == x ? x : Find(fa[x]);
}
IL void Kruskal(){
sort(_edge + 1, _edge + m + 1);
RG int t = 0;
rep(i, 1, m){
if(t == n - 1) break;
RG int u = Find(_edge[i].u), v = Find(_edge[i].v);
if(u != v){
t++; fa[u] = v;
Add(u, v, _edge[i].f); Add(v, u, _edge[i].f);
}
}
}
IL void Dfs(RG int u, RG int ans1){
if(u == n) ans = ans1;
uev(e, u){
RG int v = edge[e].to;
if(vis[v]) continue;
vis[v] = 1;
RG int f = min(ans1, edge[e].f);
Dfs(v, f);
}
}
int main(){
RG int T = Get();
rep(t, 1, T){
n = Get(); m = Get();
mem(ft, -1); ans = 2147483647; cnt = 0;
rep(i, 1, m){
RG int u = Get(), v = Get(), f = Get();
_edge[i] = (_Edge){u, v, f};
}
rep(i, 1, n) fa[i] = i;
Kruskal();
mem(vis, 0); vis[1] = 1;
Dfs(1, ans);
printf("Scenario #%d:
%d
", t, ans);
}
return 0;
}