考虑二分答案 $F$ ，那么现在的问题变成是否对于覆盖并有交集。
考虑边 $(u,v)$ ，若覆盖并在 $(u,v,w)$ 线段中，设点 $i$ 走到 $u$ 号后还能走 $F1$ , 走到 $v$ 还能走 $F2$ ，则现在要求的是一个子问题:求在 $n$ 个 $(0,F1),(w-F2+1,w)$ 中判断是否有交集，若存在点 $x$ 使得 $n$ 个线段都能被覆盖时，$x$ 肯定为 $F1$ 或 $w-F2+1$ ，所以直接暴力枚举即可，时间复杂度 $O(n^4log 值域)$。
而如何优化时间复杂度，考虑如何快速计算贡献，直接离散化后差分计算即可。
时间复杂度 $O(n^3log 值域)$。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=251; struct Edge{ int u,v,w; }x[MAXN*MAXN]; int n,m,dis[MAXN][MAXN]; double f1[MAXN][MAXN*MAXN],f2[MAXN][MAXN*MAXN],l,r,minn=LLONG_MAX,eps=1e-9,num[MAXN<<1],tmp[MAXN<<1]; int M; int G1[MAXN<<1][MAXN<<1],G2[MAXN<<1][MAXN<<1]; int NU[MAXN<<1],cnt[MAXN],Cnt; inline int Q(double res){return lower_bound(tmp+1,tmp+M+1,res)-tmp;} inline bool Query(int id,double G){ memset(NU,0,sizeof(NU));memset(cnt,0,sizeof(cnt)); int Num=0; num[++Num]=0;tmp[Num]=num[Num]; num[++Num]=x[id].w;tmp[Num]=num[Num]; for(register int i=1;i<=n;i++){ double t1=f1[i][id],t2=x[id].w-f2[i][id]; Cnt++; if(t1>=0) num[++Num]=min(t1,(double)x[id].w),tmp[Num]=num[Num]; if(f2[i][id]>=0) num[++Num]=max((double)0,t2),tmp[Num]=num[Num]; } sort(tmp+1,tmp+Num+1); M=unique(tmp+1,tmp+Num+1)-tmp-1; for(register int i=1;i<=Num;i++) Cnt++,num[i]=lower_bound(tmp+1,tmp+M+1,num[i])-tmp; for(register int i=1;i<=n;i++){ Cnt++; double t1=f1[i][id],t2=x[id].w-f2[i][id]; if(t1>=0){ int l=1,r=Q(min(t1,(double)x[id].w))+1; G1[l][++NU[l]]=i;G2[l][NU[l]]=1; G1[r][++NU[r]]=i;G2[r][NU[r]]=-1; } if(f2[i][id]>=0){ int l=Q(max((double)0,t2)); G1[l][++NU[l]]=i;G2[l][NU[l]]=1; } } int Sum=0; for(register int i=1;i<=M;i++){ for(register int j=1;j<=NU[i];j++){ Cnt++; int f=G1[i][j],opt=G2[i][j]; if(opt==1){ if(cnt[f]==0) Sum++; cnt[f]++; }else{ if(cnt[f]==1) Sum--; cnt[f]--; } }if(Sum==n) return 1; }return 0; } inline bool check(double G){ for(register int u=1;u<=n;u++){ for(register int i=1;i<=m;i++){ f1[u][i]=G-dis[u][x[i].u]; f2[u][i]=G-dis[u][x[i].v]; } } for(register int i=1;i<=m;i++) if(Query(i,G)) return 1; return 0; } int main(){ // freopen("make.in","r",stdin); n=read(),m=read(); memset(dis,127/3,sizeof(dis)); for(int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); r+=w; x[i].u=u,x[i].v=v,x[i].w=w; dis[u][v]=dis[v][u]=w; } for(int i=1;i<=n;i++) dis[i][i]=0; for(int p=1;p<=n;p++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][p]+dis[p][j]); while(l<=r){ double mid=(l+r)/2.0; if(check(mid)) minn=min(minn,mid),r=mid-eps; else l=mid+eps; }printf("%.9lf ",minn); }