之所以写个题解是因为题解区大部分题解的做法都有 bug（u1s1 周六上午在讨论区里连发两个 hack 的是我，由于我被禁言才让 ycx 代发的）
首先碰到这种期望题，我们套路地设 \(dp_u\) 为从节点 \(u\) 走到节点 \(n\) 经过的节点数的期望值，那么显然有转移方程 \(dp_u=\dfrac{1}{deg_u}(\sum\limits_{(u,v)\in E}dp_v)+1\)，由于这个 \(dp\) 方程存在环，故需按照 P3232 游走 的套路进行高斯消元，具体来说你将这 \(n\) 个 \(dp\) 转移式写成矩阵的形式高斯消元一下即可。
等等……\(10^4\) 你让我跑高斯消元？
注意到题目中有个条件，就是每个强连通分量大小 \(\le 100\)，因此考虑先将原图进行一遍 SCC 缩点，缩点完成后显然原图变成了一个 DAG，我们考虑按这个 DAG 的拓扑序倒序（或者说，以 \(t\) 为起点拓扑排序）对每个强连通分量中的点计算一遍 \(dp\) 值，具体来说我们给当前强连通分量中的所有点重新编号，对于形如 \(dp_u=\dfrac{1}{deg_u}(\sum\limits_{(u,v)\in E}dp_v)+1\) 的式子，如果 \(v\) 与 \(u\) 在同一个强连通分量中那就按照套路将式子改写成一个 \(dp_u\) 与这样的 \(dp_v\) 的关系式，否则由于我们按照拓扑序倒序计算答案，\(dp_v\) 的值肯定已经计算好了，那么我们把它当作常数项拖到右边去即可。具体实现的时候可以以 \(s\) 为起点跑一遍 tarjan，因为最终强连通分量的编号本身就是按拓扑序倒序编好号的了，就 duck 不必再写遍拓扑排序了，直接从 \(1\) 枚举到 \(\text{强连通分量个数}\) 依次计算即可。
记 \(s_i\) 为强连通分量大小，那么该算法复杂度 \(T(n)=\sum\limits_{i=1}^ms_i^3\)，而 \(s_i\le 100\)，故 \(T(n)\le\dfrac{10^4}{100}\times 100^3=10^8\)，可以通过此题。
那么什么情况输出 INF 呢？显然如果 \(s\) 不能到 \(t\) 答案肯定是 INF，接下来就是我要强调的地方了，不少题解都认为，只要存在 \(s\) 能到达但却不能到达 \(t\) 的点就 INF，但考虑下面的数据：
3 2 1 3
1 3
3 2
事实上，\(2\) 虽然能够从 \(3\) 到达，但从 \(1\to 2\) 的路径上已经经过 \(3\) 了，因此是可以到达 \(2\) 的，答案应当为 \(1.000\)。
还有的题解稍微明智些，把不能到达的点的 \(dp\) 值设为 \(\infty\)，然后判是否有 \(dp_s=\infty\)，这样做是可以避免掉上述情况的，但由于实现上出了个小 bug（如果一个点出度为 \(0\) 那么它的 \(dp\) 值就是 \(\infty\)），导致其可以被以下的数据叉掉：
5 5 1 5
1 5
1 2
2 3
3 4
4 2
我的做法是，先建反图，以 \(t\) 为起点做一遍 DFS 找出所有能到达 \(t\) 的点，然后如果一个点不能到达 \(t\) 那就令它的 \(dp\) 值为 \(\infty\)，这样又可避免上述情况。
当然我的做法可能也存在漏洞（只是我发现不了了），如果发现漏洞请及时提出，谢谢。
我认为做题还是要严谨些，愿管理员把 hack 数据加入本题的测试数据中。
那问题就来了，为什么我就不能把我 hack 的这份热情放到 CF 比赛中呢
const int MAXS=100;
const int MAXN=10000;
const int MAXM=1e6;
const double INF=1e15;
int n,m,s,t;
int hd[MAXN+5],to[MAXM*2+5],nxt[MAXM*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int bel[MAXN+5],cmp=0,dfn[MAXN+5],low[MAXN+5],tim=0;
bool vis[MAXN+5];int stk[MAXN+5],top=0;vector<int> scc[MAXN+5];
vector<int> rev[MAXN+5];bool can[MAXN+5];
void dfs(int x){
if(can[x]) return;can[x]=1;
for(int y:rev[x]) dfs(y);
}
void tarjan(int x){
dfn[x]=low[x]=++tim;vis[x]=1;stk[++top]=x;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];
if(!dfn[y]) tarjan(y),chkmin(low[x],low[y]);
else if(vis[y]) chkmin(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
cmp++;int o;
do {
o=stk[top--];vis[o]=0;
scc[bel[o]=cmp].pb(o);
} while(o!=x);
}
}
int id[MAXN+5],seq[MAXS+5],subsiz=0,deg[MAXN+5];
double dp[MAXN+5],a[MAXS+5][MAXS+5],f[MAXS+5];
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);deg[u]++;
adde(u,v);rev[v].pb(u);
}
tarjan(s);dfs(t);if(!dfn[t]) return puts("INF"),0;
for(int i=1;i<=cmp;i++){
subsiz=0;memset(a,0,sizeof(a));memset(f,0,sizeof(f));
for(int u:scc[i]){seq[++subsiz]=u;id[u]=subsiz;}
for(int u:scc[i]){
int p=id[u];
if(u==t){a[p][p]=1;continue;}
a[p][p]=a[p][subsiz+1]=deg[u];
for(int e=hd[u];e;e=nxt[e]){
int v=to[e];
if(bel[v]==bel[u]) a[p][id[v]]--;
else a[p][subsiz+1]+=dp[v];
}
if(!can[u]) a[p][subsiz+1]=INF;
}
// for(int j=1;j<=subsiz;j++) for(int k=1;k<=subsiz+1;k++)
// printf("%.3lf%c",a[j][k],(k==subsiz+1)?'\n':' ');
for(int j=1;j<=subsiz;j++){
int t=j;
for(int k=j+1;k<=subsiz;k++) if(fabs(a[k][j])>fabs(a[t][j])) t=k;
for(int k=j;k<=subsiz+1;k++) swap(a[t][k],a[j][k]);
for(int k=j+1;k<=subsiz+1;k++) a[j][k]/=a[j][j];a[j][j]=1;
for(int k=j+1;k<=subsiz;k++){
for(int l=j+1;l<=subsiz+1;l++) a[k][l]-=a[k][j]*a[j][l];
a[k][j]=0;
}
}
for(int j=subsiz;j;j--){
f[j]=a[j][subsiz+1];
for(int k=j+1;k<=subsiz;k++) f[j]-=f[k]*a[j][k];
// printf("%.3lf\n",f[j]);
}
for(int j=1;j<=subsiz;j++){
if(f[j]>1e9) dp[seq[j]]=INF;
else dp[seq[j]]=f[j];
}
}
// for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
if(dp[s]>1e9) puts("INF");
else printf("%.3lf\n",dp[s]);
return 0;
}