这道题之前我写过一个巨逗比的写法(传送门:http://www.cnblogs.com/liu-runda/p/6220381.html)
当时的原因是这道题可以抽象出和”绿豆蛙的归宿”差不多的模型,而我之前写”绿豆蛙的归宿”就是用的这个巨逗比的方法.
然后前几天看了@Sengxian的博客里”绿豆蛙的归宿”的写法(传送门:https://blog.sengxian.com/algorithms/probability-and-expected-value-dynamic-programming )发现”绿豆蛙的归宿”还可以用期望的线性性写,只需要求出经过每个点的概率(也就是期望次数,因为是DAG上所以这里经过的概率和期望次数是一样的),加起来就是总共期望经过的点数,点数-1就是期望步数.感觉非常兹瓷,于是写了写这个题,顺便试了一下之前口胡的把所有状态按最短路长度排序然后DP的方法,发现过不了….无用的状态太多了会TLE.把之前那个逗比程序(求出走到每个状态的概率和从起点到这个状态的期望步数),改了改过了(不过似乎没有快多少的样子,应该是因为之前逗比代码用的dijkstra...).
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
struct edge{
int to,next;
}lst[maxn<<];int len=,first[maxn];
void addedge(int a,int b){
lst[len].to=b;lst[len].next=first[a];
first[a]=len++;
}
double p[maxn][maxn],e[maxn][maxn];
int g[maxn][maxn],dis[maxn][maxn];
int n,m,s0,t0;
struct node{
int v,d;
node(int _v,int _d){v=_v;d=_d;}
bool operator <(const node &B)const{
return d>B.d;
}
};
int vis[maxn];
int T;
void dijkstra(int s,int dis[]){
++T;
priority_queue<node> q;
q.push(node(s,));
while(!q.empty()){
node tmp=q.top();q.pop();
if(vis[tmp.v]==T)continue;
vis[tmp.v]=T;dis[tmp.v]=tmp.d;
for(int pt=first[tmp.v];pt;pt=lst[pt].next){
if(vis[lst[pt].to]!=T)q.push(node(lst[pt].to,tmp.d+));
}
}
int ans;
for(int i=;i<=n;++i){
ans=i;
for(int pt=first[i];pt;pt=lst[pt].next){
if(dis[lst[pt].to]<dis[ans])ans=lst[pt].to;
if(dis[lst[pt].to]==dis[ans]&&lst[pt].to<ans)ans=lst[pt].to;
}
g[i][s]=ans;
}
}
int deg[maxn];
struct Node{
int s,t;
Node(int _s,int _t){s=_s;t=_t;}
Node(){};
}q[][maxn*maxn];//q[0]:-1 q[1]:-2 q[2]:-3
int head[],tail[];
bool used[maxn][maxn];
double ans=;
void bfs(){
while((head[]!=tail[])||(head[]!=tail[])||(head[]!=tail[])){
// getchar();printf("%d %d\n",head[0],tail[0]);
int tmp=-,Max=-;
for(int i=;i<;++i){
if(head[i]!=tail[i]&&dis[q[i][head[i]].s][q[i][head[i]].t]>Max){
tmp=i;Max=dis[q[i][head[i]].s][q[i][head[i]].t];
}
}
Node x=q[tmp][head[tmp]++];
ans+=p[x.s][x.t];
if(x.s==x.t)continue;
int s1=g[g[x.s][x.t]][x.t];
if(s1==x.t){
p[s1][x.t]+=p[x.s][x.t];//ans+=p[x.s][x.t];
if(!used[s1][x.t]){
used[s1][x.t]=true;
if(dis[x.s][x.t]==){
q[][tail[]++]=Node(s1,s1);
}else{
q[][tail[]++]=Node(s1,s1);
}
}
}else{
for(int pt=first[x.t];pt;pt=lst[pt].next){
p[s1][lst[pt].to]+=p[x.s][x.t]/deg[x.t];
if(!used[s1][lst[pt].to]){
used[s1][lst[pt].to]=true;
if(dis[s1][lst[pt].to]==dis[x.s][x.t]-)q[][tail[]++]=Node(s1,lst[pt].to);
else if(dis[s1][lst[pt].to]==dis[x.s][x.t]-)q[][tail[]++]=Node(s1,lst[pt].to);
else q[][tail[]++]=Node(s1,lst[pt].to);
}
}
// p[s1][x.t]+=p[x.s][x.t]/deg[x.t];
// if(q[1][tail[1]++]=Node(s1,x.t);
} }
}
int main(){
scanf("%d%d",&n,&m);
scanf("%d%d",&s0,&t0);
int a,b;
for(int i=;i<=m;++i){
scanf("%d%d",&a,&b);deg[a]++;deg[b]++;
addedge(a,b);addedge(b,a);
}
for(int i=;i<=n;++i){
deg[i]++;addedge(i,i);
dijkstra(i,dis[i]);
}
p[s0][t0]=1.0;
q[][tail[]++]=Node(s0,t0);
bfs();//get possibility
printf("%.3f\n",ans-);
return ;
}