51nod

分析

假设答案位置在某条边上，感性理解可得答案关于答案位置与这条边的某个端点的距离是单谷函数。

枚举答案在哪条边上并三分，问题变为求最远点。显然某个点到达边上某个位置一定是先到达一个端点再走过来，因此 Floyd 预处理两两之间的最短路即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200+10,M=20000+10;

int n,m;
int dis[N][N];
struct edge { int u,v,w; } e[M];

double f(double x,int u,int v,int w) {
    double res=0;
    for (int i=1;i<=n;++i)
        res=max(res,min(dis[i][u]+x,dis[i][v]+w-x));
    return res;
}

int main() {
    n=read(),m=read();
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=m;++i) {
        e[i]=(edge){read(),read(),read()};
        dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=e[i].w;
    }
    for (int i=1;i<=n;++i) dis[i][i]=0;
    for (int k=1;k<=n;++k)
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    double ans=1e18;
    for (int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        double L=0,R=w;
        while (R-L>1e-10) {
            double a=(L+L+R)/3,b=(L+R+R)/3;
            if (f(a,u,v,w)<f(b,u,v,w)) R=b;
            else L=a;
        }
        ans=min(ans,f(L,u,v,w));
    }
    printf("%.9lf\n",ans);
    return 0;
}