//给你一个无向连通图,找一个点使得它到这个图最短路中最大的距离最短//可以遍历所有边，对于每条边有的连个顶点u,v//可以通过这两个点将这个图分左边，u-v边,右边三个部分//但是哪些点分在左边，哪些点分在右边，如果暴力所有情况显然会超时//用一个二维数组存入所有点到u,v两个点的最短路//将其排序，对于a[i].u >=a[j].u ,a[i].v >= a[j].v 的点，可以用i点代替j点//那么剩下的点会出现u递增，v递减，所以如果从i分为左右两边那么i左边的最大值为a[i-1].u#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std ;const int maxn = 210 ;const int maxm = maxn*maxn ;const int inf = 0x3f3f3f3f;int x[maxm] ,y[maxm] ;int edge[maxn][maxn] ;int len[maxn*maxn] ;pair<int , int> a[maxm] , b[maxm] ;int n , m ;void floyd(){ for(int k = 1;k <= n;k++) for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) edge[i][j] = min(edge[i][k] + edge[k][j] , edge[i][j]) ;}double solve(){ floyd() ; int ans = inf ; for(int i = 1;i <= m;i++) { int u = x[i] ; int v = y[i] ; for(int j = 1;j <= n;j++) a[j] = make_pair(edge[u][j] , edge[v][j]) ; sort(a+1 , a+1+n) ; int k = 0; for(int j = 1;j <= n;j++) { while(k && a[j].second >= b[k].second) k– ; b[++k] = a[j]; } if(k == 1)ans =min(ans , min(b[1].first , b[1].second)) ; else for(int j = 2;j <= k;j++) ans = min(ans , (b[j-1].first + b[j].second + len[i])>>1) ; } return (double)ans/2 ;}int main(){ while(~scanf("%d%d" ,&n , &m)) { int u , v , w ; for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) edge[i][j] = i==j ? 0:inf ; for(int i = 1;i <= m;i++) { scanf("%d%d%d" ,&u , &v , &w) ; edge[u][v] = edge[v][u] = 2*w ; len[i] = 2*w ; x[i] = u ;y[i] = v ; } printf("%lf\n" ,solve()); } return 0;}
，人之所以能，是相信能。
