首先每个点直接走到点 (n) 的期望天数是知道的，所以可以将点 (n) 加入忽略集合，然后在剩下点中走来走去。
对于当前期望天数最少的那个点 (i)，能走到点 (n) 就走，否则走自环。因为走到其它点最终也必须走到点 (n)，而它们的期望天数都大于点 (i)。将点 (i) 接入忽略集合。
同样地，我们接着找出通过点 (i) 间接走到或不通过点 (i) 直接走到点 (n) 期望天数最小的点加入忽略集合。
重复上述过程，即每次找出仅通过忽略集合中的点或走自环到达点 (n) 期望天数最小的点加入忽略集合，更新贡献。类似 Dijkstra，正确性来源于路径的确定性。
问题就是如何计算。考虑枚举每条边：
[E(u)=1+left(sum_i^{E(i)<E(u)}E(i) imes p_{u,i} imesprod_{j}^{E(j)<E(i)}1-p_{u,j}
ight)+E(u) imesprod_i^{E(i)<E(u)}1-p_{u,i}
]
[E(u) imesleft(1-prod_i^{E(i)<E(u)}1-p_{u,i}
ight)=1+left(sum_i^{E(i)<E(u)}E(i) imes p_{u,i} imesprod_{j}^{E(j)<E(i)}1-p_{u,j}
ight)
]
[E(u)=largefrac{1+sumlimits_i^{E(i)<E(u)}E(i) imes p_{u,i} imesprodlimits_{j}^{E(j)<E(i)}1-p_{u,j}}{1-prodlimits_i^{E(i)<E(u)}1-p_{u,i}}
]
分不走自环和走自环两种情况。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define Db double
#define For(i,x,y)for(i=x;i<=(y);i++)
bool vis[N];
Db p[N][N],now[N],e[N];
int read()
{
int A;
bool K;
char C;
C=A=K=0;
while(C<'0'||C>'9')K|=C=='-',C=getchar();
while(C>'/'&&C<':')A=(A<<3)+(A<<1)+(C^48),C=getchar();
return(K?-A:A);
}
int main()
{
int n,i,j,o;
n=read();
For(i,1,n)
For(j,1,n)p[i][j]=Db(read())/100.0;
vis[n]=1;
For(i,1,n)now[i]=1.0-p[i][n];
j=n;
For(o,1,n-1)
{
j=1;
For(i,2,n)
if(!vis[i]&&(e[i]+1.0)/(1.0-now[i])<(e[j]+1.0)/(1.0-now[j]))j=i;
vis[j]=1;
e[j]=(1.0+e[j])/(1.0-now[j]);
For(i,1,n)
if(!vis[i])e[i]+=e[j]*p[i][j]*now[i];
if(j==1)cout<<fixed<<setprecision(7)<<e[1],exit(0);
For(i,1,n)
if(!vis[i])now[i]*=1.0-p[i][j];
}
cout<<fixed<<setprecision(7)<<e[1];
return 0;
}