题意
给你n个点，1为起点，2为终点，要求所有1到2所有路径中每条路径上最大值的最小值。
思路
不想打最短路
跑一边最小生成树，再扫一遍1到2的路径，取最大值即可
注意g++要用%f输出！！！
常数巨大的丑陋代码
# 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;
# define Sqr(a) ((a) * (a))
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;
struct Edge{
int to, nt;
double f;
} edge[MAXN<<1];
struct _Edge{
int u, v;
double f;
IL bool operator < (_Edge b) const{
return f < b.f;
}
} _edge[MAXN];
double ans, x[MAXN], y[MAXN];
IL void Add(RG int u, RG int v, RG double 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 double ans1){
if(u == 2) ans = ans1;
uev(e, u){
RG int v = edge[e].to;
if(vis[v]) continue;
vis[v] = 1;
RG double f = max(ans1, edge[e].f);
Dfs(v, f);
}
}
int main(){
RG int T = 0;
n = Get();
while(n){
T++;
mem(ft, -1); m = ans = cnt = 0;
rep(i, 1, n) scanf("%lf%lf", &x[i], &y[i]);
rep(i, 1, n-1) rep(j, i+1, n){
double dis = sqrt(Sqr(x[i] - x[j]) + Sqr(y[i] - y[j]));
_edge[++m] = (_Edge){i, j, dis};
}
rep(i, 1, n) fa[i] = i;
Kruskal();
mem(vis, 0); vis[1] = 1;
Dfs(1, 0);
printf("Scenario #%d
Frog Distance = %.3f
", T, ans);
n = Get();
}
return 0;
}