bzoj 1415 [Noi2005]聪聪和可可 概率dp

先dijkstra跑出两点间最短路。
g[i][j] 表示猫在i，老鼠在j时猫下一步走到的位置。
f[i][j] 表示猫在i，老鼠在j时的期望步数。
f[i][j] 按i到j最短路从小到大转移。

#include <bits/stdc++.h>
using namespace std;
#define N 1100
int n,m,S,T,tot,cnt;
int head[N],nex[N<<1],to[N<<1];
priority_queue<pair<int,int> >q;
int mp[N][N],vis[N],g[N][N],du[N];
double f[N][N];
struct node
{
    int x,y,v;
    node(){}
    node(int x,int y):x(x),y(y){v=mp[x][y];}
    friend bool operator < (const node &r1,const node &r2)
        {return r1.v<r2.v;}
}a[N*N];
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dijkstra(int x)
{
    memset(vis,0,sizeof(vis));
    memset(mp[x],0x3f,sizeof(mp[x]));
    mp[x][x]=0;q.push(make_pair(0,x));
    while(!q.empty())
    {
        int t=q.top().second;q.pop();
        if(vis[t])continue;
        vis[t]=1;
        for(int i=head[t];i;i=nex[i])
            if(mp[x][to[i]]>mp[x][t]+1)
            {
                mp[x][to[i]]=mp[x][t]+1;
                q.push(make_pair(-mp[x][to[i]],to[i]));
            }
    }
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        du[x]++;du[y]++;
    }
    for(int i=1;i<=n;i++)
        dijkstra(i);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=head[i];k;k=nex[k])
                if(!g[i][j]||mp[g[i][j]][j]>mp[to[k]][j]||
                (mp[g[i][j]][j]==mp[to[k]][j]&&g[i][j]>to[k]))
                        g[i][j]=to[k];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)a[++cnt]=node(i,j);
    sort(a+1,a+1+cnt);
    for(int i=1;i<=cnt;i++)
    {
        int t1=g[a[i].x][a[i].y],t2=g[t1][a[i].y];
        if(t1==a[i].y||t2==a[i].y)
            {f[a[i].x][a[i].y]=1;continue;}
        f[a[i].x][a[i].y]=f[t2][a[i].y]+1;
        for(int j=head[a[i].y];j;j=nex[j])
            f[a[i].x][a[i].y]+=f[t2][to[j]]+1;
        f[a[i].x][a[i].y]/=(du[a[i].y]+1);
    }
    printf("%.3lf\n",f[S][T]);
    return 0;
}