题目链接：

题目：

题解：

设$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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef double db;const int N=1e5+15;int n,m,tot;int head[N],vis[N],cnt[N];db sum[N];struct EDGE{ int to,nxt;}edge[N<<1];struct node{ int x,cnt;db sum;};priority_queue
           
             q;bool operator < (node a,node b) { return a.sum*b.cnt>b.sum*a.cnt;}inline int read(){ char ch=getchar();int s=0,f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';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=1;i<=m;i++) { int u=read(),v=read(); add(u,v);add(v,u); } cnt[n]=1; q.push((node){n,1,0}); while (!q.empty()) { int x=q.top().x;q.pop(); if (vis[x]) continue; vis[x]=1; 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]==0||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[1]+m)/cnt[1]); return 0;}