因为聪聪每次走两步，可可每次最多走一步，所以距离一定递减，状态不会有环
于是预处理一下每两点之间距离然后模拟走的过程，记忆化搜索即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// <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; } |
说点什么