bzoj1415 NOI2005聪聪和可可
阅读原文时间:2023年07月10日阅读:3

%%%http://hzwer.com/2819.html

先各种暴力搞出来p[x][y](从x到y下一个最近应该到达的位子)

然后就记忆化搜索??(雾)

#include
#define LL long long
#define LD long double
#define N 100005
using namespace std;
inline int ra()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
const int M=;
int n,m,cnt,a,b;
int head[M],d[M],q[N];
int dis[M][M],p[M][M];
double f[M][M];
struct node{
int to,next;
}e[M<<];
void insert(int x, int y)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
d[x]++;
}
double dp(int x, int y)
{
if (f[x][y]) return f[x][y];
if (x==y) return ;
if (p[x][y]==y || p[p[x][y]][y]==y) return f[x][y]=;
double tot=dp(p[p[x][y]][y],y);
for (int i=head[y];i;i=e[i].next)
tot+=dp(p[p[x][y]][y],e[i].to);
return f[x][y]=tot/(d[y]+)+;
}
void bfs(int x)
{
int l=,r=;
q[]=x; dis[x][x]=;
while (l<r)
{
int now=q[l++],tmp=p[x][now];
for (int i=head[now];i;i=e[i].next)
if (dis[x][e[i].to]==- || (+dis[x][now]==dis[x][e[i].to] && tmp<p[x][e[i].to]))
{
dis[x][e[i].to]=dis[x][now]+;
p[x][e[i].to]=tmp;
if (!tmp) p[x][e[i].to]=e[i].to;
q[r++]=e[i].to;
}
}
}
int main()
{
memset(dis,-,sizeof(dis));
n=ra(); m=ra(); a=ra(); b=ra();
for (int i=; i<=m; i++)
{
int x=ra(),y=ra();
insert(x,y); insert(y,x);
}
for (int i=; i<=n; i++) bfs(i);
printf("%.3lf",dp(a,b));
return ;
}