CERC2017 Gambling Guide，最短路变形，期望dp

题目链接

题面链接

题意

给定一个无向图，你需要从 1 $1$点出发到达 n $n$点，你在每一点的时候，使用 1 $1$个单位的代价，随机得到相邻点的票，但是你可以选择留在原地，也可以选择使用掉这张票，问到达 n $n$点的最小代价的方案的期望是多少。

题解

我们先假定在最优方案下从每个点 x $x$出发，到达 n $n$点的代价的期望为 ex $e_x$，那么显然，我们可以列出方程 ex=∑min(ex,ey)degx+1 $e_x=\frac{\sum min(e_x,e_y)}{de{g}_x}+1$，其中 y $y$与 x $x$节点相连。初值 dpn=0 $d{p}_n=0$。

借鉴 GXZlegend $GXZlegend$的一句话，遇见“初始值只有一个点的 dp $dp$值确定,其他点的 dp $dp$值依赖于已经计算出来的点的 dp $dp$值”这种类型的题，往往考虑使用最短路的方式转移。

观察方程，如果我们按照计算出来的 ex $e_x$从小到大的方式遍历的话，那么先计算出来的 ex $e_x$一定不会再被后计算出来的值更新，满足跟最短路一样的性质。

我们一开始假定所有的 ex|x!=n=inf $e_{x|x!=n}=inf$,并且 en=0 $e_n=0$，每个点的 min(ex,ey) $min(e_x,e_y)$都取 ex $e_x$。

那么我们模拟一下这个转移过程，当前从堆里取出的点是 u $u$，相邻的点有 v $v$,我们发现 v $v$是第一次被更新，因为 ev=inf $e_v=inf$，满足 ev>eu $e_v>e_u$，那么 v $v$就要被更新，即根据方程 ev=(degv−1)ev+eudegv+1 $e_v=\frac{(de{g}_v-1)e_v+e_u}{de{g}_v}+1$，那么 ev=eu+degv $e_v=e_u+de{g}_v$。
如果接下来某次取出的点是 p $p$，相邻的点还有 v $v$，并且 ev>ep $e_v>e_p$，那么 ev $e_v$就要被二次更新了，也就是 ev=(degv−2)ev+eu+epdegv+1 $e_v=\frac{(de{g}_v-2)e_v+e_u+e_p}{de{g}_v}+1$，那么 ev=eu+ep+degv2 $e_v=\frac{e_u+e_p+de{g}_v}{2}$。依次类推。

代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 300007;
const double inf = 1e9;
int n,m;
vector<int> G[maxn];
typedef pair<double,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > Q;
double dp[maxn];
int deg[maxn],vis[maxn];
int usedeg[maxn];
void dij(){
    for(int i = 1;i < n;++i) dp[i] = inf;
    Q.push({0,n});
    vis[n] = 1;
    while(!Q.empty()){
        pii p = Q.top();Q.pop();
        int u = p.second;
        double nowdp = p.first;
        if(nowdp > dp[u]) continue;
        for(int v:G[u]){
            if(!vis[v]){
                vis[v] = 1;
                usedeg[v] = 1;
                dp[v] = nowdp+deg[v];
                Q.push({dp[v],v});
            }
            else if(nowdp < dp[v]){
                double c = dp[v]*usedeg[v]-deg[v];
                usedeg[v]++;
                dp[v] = (c+nowdp+deg[v])/usedeg[v];
                Q.push({dp[v],v});
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i = 0;i < m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
        deg[u] ++,deg[v] ++;
    }
    dij();
    printf("%.12lf\n",dp[1]);

}