题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1415
乍一看和“游走”一样。于是高斯消元。n^2状态，复杂度n^6……
看看TJ，发现因为聪聪不是随便走的，所以聪聪一直逼近可可。故其实无环。可以记搜。
（1A还是不错的）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=;
int n,m,l0,l1,nxt[N][N],dfn[N],du[N];
double dp[N][N];
bool vis[N],vs[N][N];
priority_queue<int,vector<int>,greater<int> >ed[N];
void add(int x,int y)
{
ed[x].push(y);ed[y].push(x);
du[x]++;du[y]++;
}
void bfs(int cr)
{
priority_queue<int,vector<int>,greater<int> >tp;
memset(vis,,sizeof vis);memset(dfn,,sizeof dfn);
queue<int> q;q.push(cr);vis[cr]=;nxt[cr][cr]=cr;
while(q.size())
{
int k=q.front();q.pop();
tp=ed[k];
while(tp.size())
{
int v=tp.top();tp.pop();
if(vis[v])continue;
dfn[v]=dfn[k]+;vis[v]=;q.push(v);
if(dfn[v]>)nxt[v][cr]=nxt[k][cr];
else nxt[v][cr]=v;
}
}
}
double dfs(int x,int y)//coco->x ,cncn->y
{
// printf("x=%d y=%d\n",x,y);
if(vs[x][y])return dp[x][y];vs[x][y]=;
if(nxt[x][y]==x){/*printf("rt x=%d y=%d\n",x,y);*/return dp[x][y]=;}
double ret=(dfs(x,nxt[x][y])+(nxt[x][y]!=x))/(du[x]+);
priority_queue<int,vector<int>,greater<int> >tp=ed[x];//每层定义
// printf("siz[%d]=%d\n",x,tp.size());
while(tp.size())
{
int v=tp.top();tp.pop();
// printf("v=%d nxt[%d][%d]=%d\n",v,x,y,nxt[x][y]);
ret+=(dfs(v,nxt[x][y])+(nxt[x][y]!=v))/(du[x]+);
}
// printf("ret=%.3lf\n",ret);
return dp[x][y]=ret;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&l0,&l1);int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);add(x,y);
}
for(int i=;i<=n;i++)bfs(i);
printf("%.3lf",dfs(l1,l0));
return ;
}
版本1
看看TJ，发现判断得那么纠结是因为x==y时正常应返回0。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=;
int n,m,l0,l1,nxt[N][N],dfn[N],du[N];
double dp[N][N];
bool vis[N],vs[N][N];
priority_queue<int,vector<int>,greater<int> >ed[N];
void add(int x,int y)
{
ed[x].push(y);ed[y].push(x);
du[x]++;du[y]++;
}
void bfs(int cr)
{
priority_queue<int,vector<int>,greater<int> >tp;
memset(vis,,sizeof vis);memset(dfn,,sizeof dfn);
queue<int> q;q.push(cr);vis[cr]=;nxt[cr][cr]=cr;
while(q.size())
{
int k=q.front();q.pop();
tp=ed[k];
while(tp.size())
{
int v=tp.top();tp.pop();
if(vis[v])continue;
dfn[v]=dfn[k]+;vis[v]=;q.push(v);
if(dfn[v]>)nxt[v][cr]=nxt[k][cr];
else nxt[v][cr]=v;
}
}
}
double dfs(int x,int y)//coco->x ,cncn->y
{
if(vs[x][y])return dp[x][y];vs[x][y]=;
if(x==y)return dp[x][y]=;//
if(nxt[x][y]==x)return dp[x][y]=;
double ret=dfs(x,nxt[x][y])/(du[x]+)+;
priority_queue<int,vector<int>,greater<int> >tp=ed[x];//每层定义
while(tp.size())
{
int v=tp.top();tp.pop();
ret+=dfs(v,nxt[x][y])/(du[x]+);
}
return dp[x][y]=ret;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&l0,&l1);int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);add(x,y);
}
for(int i=;i<=n;i++)bfs(i);
printf("%.3lf",dfs(l1,l0));
return ;
}
版本2
但是自己代码巨慢……想来是用了优先队列的缘故（为了标号字典序）。尝试改一改。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=;
int n,m,l0,l1,nxt[N][N],dfn[N],du[N],head[N],xnt;
double dp[N][N];
bool vis[N],vs[N][N];
priority_queue<int,vector<int>,greater<int> >ed[N];
struct Edge{
int next,to;
Edge(int n=,int t=):next(n),to(t) {}
}edge[N<<];
void add(int x,int y)
{
edge[++xnt]=Edge(head[x],y);head[x]=xnt;
edge[++xnt]=Edge(head[y],x);head[y]=xnt;
ed[x].push(y);ed[y].push(x);
du[x]++;du[y]++;
}
void bfs(int cr)
{
priority_queue<int,vector<int>,greater<int> >tp;
memset(vis,,sizeof vis);memset(dfn,,sizeof dfn);
queue<int> q;q.push(cr);vis[cr]=;nxt[cr][cr]=cr;
while(q.size())
{
int k=q.front();q.pop();
tp=ed[k];
while(tp.size())
{
int v=tp.top();tp.pop();
if(vis[v])continue;
dfn[v]=dfn[k]+;vis[v]=;q.push(v);
if(dfn[v]>)nxt[v][cr]=nxt[k][cr];
else nxt[v][cr]=v;
}
}
}
double dfs(int x,int y)//coco->x ,cncn->y
{
if(vs[x][y])return dp[x][y];vs[x][y]=;
if(x==y)return dp[x][y]=;//
if(nxt[x][y]==x)return dp[x][y]=;
double ret=dfs(x,nxt[x][y])/(du[x]+)+;
for(int i=head[x];i;i=edge[i].next)
ret+=dfs(edge[i].to,nxt[x][y])/(du[x]+);
return dp[x][y]=ret;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&l0,&l1);int x,y;
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);add(x,y);
}
for(int i=;i<=n;i++)bfs(i);
printf("%.3lf",dfs(l1,l0));
return ;
}
结果只是快了28ms。
别人用一些方法保证字典序。
这个人bfs+两步保证dis最小的前提下调整标号至最小。https://blog.csdn.net/clove_unique/article/details/62237321
这个人spfa的同时判断标号。（但只能记录一步的pre）https://blog.csdn.net/PoPoQQQ/article/details/40896403（bfs因为是bfs所以不能边求dis边调整标号）
可是我都没记录dis。用的dfn。所以懒得改了……比较欣赏第一个人的写法。