【BZOJ1415】【NOI2005】聪聪和可可

因为聪聪每次走两步，可可每次最多走一步，所以距离一定递减，状态不会有环

于是预处理一下每两点之间距离然后模拟走的过程，记忆化搜索即可

// <1415.cpp> - Wed Mar  8 09:18:15 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
#define next NEXT
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=1010;
const int MAXM=2010;
const int INF=1e9;
int bt,b[MAXN],next[MAXM],to[MAXM],d[MAXN];
inline void add(int x,int y){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;d[x]++;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;d[y]++;
}
int dis[MAXN][MAXN];
double f[MAXN][MAXN];
int get(int s,int t){
    int g=s;
    for(int i=b[s];i;i=next[i])
        if(dis[to[i]][t]<dis[g][t]||(dis[to[i]][t]==dis[g][t]&&to[i]<g))g=to[i];
    return g;
}
double work(int s,int t){
    if(s==t)return 0;
    if(f[s][t])return f[s][t];
    int g=get(get(s,t),t);
    if(g==t)return 1;
    f[s][t]=1+work(g,t)/(d[t]+1);
    for(int i=b[t];i;i=next[i])f[s][t]+=work(g,to[i])/(d[t]+1);
    return f[s][t];
}
queue <int> q;
int main(){
    int n=gi(),m=gi(),s=gi(),t=gi();
    for(int i=1;i<=m;i++)add(gi(),gi());
    for(int i=1;i<=n;i++){
        q.push(i);
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int j=b[x];j;j=next[j]){
                if(to[j]==i||dis[i][to[j]])continue;
                dis[i][to[j]]=dis[i][x]+1;
                q.push(to[j]);
            }
        }
    }
    printf("%.3lf",work(s,t));
    return 0;
}

// <1415.cpp> - Wed Mar 8 09:18:15 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

#define next NEXT

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=1010;

const int MAXM=2010;

const int INF=1e9;

int bt,b[MAXN],next[MAXM],to[MAXM],d[MAXN];

inline void add(int x,int y){

next[++bt]=b[x];b[x]=bt;to[bt]=y;d[x]++;

next[++bt]=b[y];b[y]=bt;to[bt]=x;d[y]++;

}

int dis[MAXN][MAXN];

double f[MAXN][MAXN];

int get(int s,int t){

int g=s;

for(int i=b[s];i;i=next[i])

if(dis[to[i]][t]<dis[g][t]||(dis[to[i]][t]==dis[g][t]&&to[i]<g))g=to[i];

return g;

}

double work(int s,int t){

if(s==t)return 0;

if(f[s][t])return f[s][t];

int g=get(get(s,t),t);

if(g==t)return 1;

f[s][t]=1+work(g,t)/(d[t]+1);

for(int i=b[t];i;i=next[i])f[s][t]+=work(g,to[i])/(d[t]+1);

return f[s][t];

}

queue <int> q;

int main(){

int n=gi(),m=gi(),s=gi(),t=gi();

for(int i=1;i<=m;i++)add(gi(),gi());

for(int i=1;i<=n;i++){

q.push(i);

while(!q.empty()){

int x=q.front();q.pop();

for(int j=b[x];j;j=next[j]){

if(to[j]==i||dis[i][to[j]])continue;

dis[i][to[j]]=dis[i][x]+1;

q.push(to[j]);

}

printf("%.3lf",work(s,t));

return 0;

}