标签：二分
题目
n,m<=1000
分析
主要问题在于存在自环，每次可以重复绕自己
把每个点的出边从小到大排序
同时把另一端端点到终点的距离从小到大排序
计算的是n * m种配对中最小的和的期望
可以枚举每个和
将所有大于等于它的概率统计进入答案，概率扫描的时候需要用优先队列简单维护
但我们不确定距离x，所以需要二分这个参数
对每个点求一遍就可以得到答案
\[时间复杂度O(n * m\log ANS)\]code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e16
#define eps 1e-12
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
struct edge{int to,next;double z;}e[maxn<<1];
struct Q{double z;int x;};
inline bool operator > (Q a,Q b){return a.z>b.z;}
double b[maxn],c[maxn],f[maxn],l,r,mid;
int last[maxn],id[maxn],n,m,S,T,cnt,cnt1,cnt2;
bool p[maxn],P[maxn];
priority_queue <Q,vector <Q> ,greater <Q> > que;
inline double doit(){
while(!que.empty())que.pop();
cnt=cnt1;
rep(i,0,cnt-1)que.push((Q){b[i]+c[0],i}),id[i]=cnt;
double re=0,p=1;
while(!que.empty()&&p>eps){
Q now=que.top();
int x=now.x;
double P=p*(id[x]-x-1)/(id[x]-x);
id[x]--;re+=(p-P)*now.z;p=P;que.pop();
if(id[x]>x)que.push((Q){b[x]+c[cnt-id[x]],x});else break;
}
return re;
}
void dfs(int x){
p[x]=1;
if(x==T){P[x]=1;return;}
reg(x){
if(!p[e[i].to])dfs(e[i].to);
P[x]|=P[e[i].to];
}
if(!P[x]){f[x]=inf;return;}
cnt1=cnt2=0;l=0,r=1e5;
reg(x)b[cnt1++]=e[i].z;
sort(b,b+cnt1);
rep(num,1,40){
mid=(l+r)/2,cnt2=0;
reg(x)c[cnt2++]=((e[i].to==x)?mid:f[e[i].to]);
sort(c,c+cnt2);
if(mid<doit())l=mid;else r=mid;
}
f[x]=l;
}
int main()
{
n=read(),m=read(),S=read(),T=read();
rep(i,1,m){
int u=read(),v=read();
scanf("%lf",&e[i].z);
e[i].to=v,e[i].next=last[u],last[u]=i;
}
dfs(S);
printf("%.8lf\n",f[S]);
return 0;
}
