( •̀ ω •́ )y
好fan
题解
#include <bits/stdc++.h>
using namespace std;
inline int read(){
char c;int f=1,res=0;
while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res*f;
}
const int inf=1e9;
double p[1005][1005],f[1005],g[1005],h[1005];
int q[1005],tot,n;
bool vis[1005];
inline void upd(){
int j=q[tot];
for(rint i=1;i<=n;++i){
if(vis[i])continue;
g[i]+=f[j]*p[i][j]*h[i];
h[i]*=1-p[i][j];
f[i]=g[i]/(1-h[i]);
}
}
inline void solve(){
for(rint i=1;i<n;++i)
f[i]=g[i]=h[i]=1;
f[n]=0;h[n]=1;
vis[n]=true;
q[++tot]=n;upd();
while(tot<n){
int id;double v=inf;
for(rint i=1;i<=n;++i)
if(!vis[i]&&f[i]<v)
v=f[i],id=i;
vis[id]=true;
q[++tot]=id;upd();
}
}
int main(){
n=read();
if(n==1){return puts("0"),0;}
for(rint i=1;i<=n;++i)for(rint j=1;j<=n;++j)p[i][j]=read()/100.0;
solve();
printf("%.8lf",f[1]);
return 0;
}
标签:CF605E,int,res,isdigit,1005,getchar
From: https://www.cnblogs.com/zan-mei-tai-yang/p/18408930