题目链接：
https://jzoj.net/senior/#main/show/6101
题目：
题解：
设$f_i$表示从节点$i$到节点$n$的期望时间，$f_n=0$
最优策略就是如果从$i,j$之间存在边且$f_j<f_i$的话，那么就从$i$走到$j$
有$f_i=\frac{1}{m}(\sum_{link[i][j]=1}min(f_i,f_j))+1+\frac{m-du_i}{m}f_i$
$du_i$是$i$的度数
即$du_if_i=\sum_{link[i][j]=1}min(f_i,f_j)+m$
右边可以写成$vf_i+(\sum_{link[i][j]=1,f_j<f_i}f_j)$的形式
继续化简得到$(du_i-v)f_i=m+(\sum_{link[i][j]=1,f_j<f_i}f_j)$
注意到$du_i-v$与左边累加的$f_j$的个数是一样的
不妨设$z=du_i-v$，$s=\sum_{link[i][j]=1,f_i<f_j}f_j$
那么$f_i=\frac{s+m}{z}$
当我们要添加新的$f_j$来更新$f_i$时，设新加的$f_j$为$a$
$f_i^,=\frac{s+m+a}{z+1}$，假设$f_i^,<f_i$，即得到更优的答案
那么化简可得$f_j=a<\frac{s+m}{z}=f_i$，刚好满足约束条件$f_j<f_i$
即我们只要把比当前的$f_i$小的$f_j$用来更新$f_i$，那么就可以得到更优的答案
这个时候我们想到了类似$dijkstra$的算法，即每次取出最小的$f_i$来更新周围的点
虽然我仍然觉得代码的正确性并不显然，各位有什么好的想法可以告诉我
代码：
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
typedef double db; const int N=1e5+;
int n,m,tot;
int head[N],vis[N],cnt[N];
db sum[N];
struct EDGE
{
int to,nxt;
}edge[N<<];
struct node
{
int x,cnt;db sum;
};
priority_queue<node> q;
bool operator < (node a,node b) {return a.sum*b.cnt>b.sum*a.cnt;}
inline int read()
{
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void add(int u,int v)
{
edge[++tot]=(EDGE){v,head[u]};
head[u]=tot;
}
int main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
n=read();m=read();
for (int i=;i<=m;i++)
{
int u=read(),v=read();
add(u,v);add(v,u);
}
cnt[n]=;
q.push((node){n,,});
while (!q.empty())
{
int x=q.top().x;q.pop();
if (vis[x]) continue;
vis[x]=;
db val=(sum[x]+m*(x!=n))/(1.0*cnt[x]);
for (int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if (cnt[y]==||val*cnt[y]<(sum[y]+m))
{
sum[y]+=val;
cnt[y]++;
if (!vis[y]) q.push((node){y,cnt[y],sum[y]+m});
}
}
}
printf("%.10lf\n",(sum[]+m)/cnt[]);
return ;
}