CF605E

https://www.cnblogs.com/cjyyb/p/9707853.html
https://www.cnblogs.com/daklqw/p/12009106.html
每次应该找出边中期望天数\(E(x)\)尽量小的走过去
假设找出了一个排列\(P\)使得\(E(P_i)\)随\(i\)单调不降

除掉\(1-\prod p\)是因为有这个概率所有边都走不了所以只能停留在原地
大概是类似dij一样每次取出\(E(x)\)最小的\(x\)更新别人 但不是很会证明正确性 具体还是看daklqw博客吧...

#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<‘:‘<<x<<endl
#define prev pku
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
	return x*f;
}
void wr(int x){
	if(x<0)putchar(‘-‘),x=-x;
	if(x>=10)wr(x/10);
	putchar(‘0‘+x%10);
}
const int MAXN=1e3+10;
double P[MAXN][MAXN];
double dis[MAXN],prod[MAXN],tmp[MAXN];bool vis[MAXN];
int n;
main(){
	n=read();
	fp(i,1,n)fp(j,1,n)P[i][j]=1.0*read()/100.0;
	fp(i,0,n-1)dis[i]=1e100,tmp[i]=prod[i]=1;
	fp(i,1,n){
		int u=0;
		fp(j,1,n)if(!vis[j]&&dis[u]>dis[j])u=j;
		if(u==1){printf("%.10lf\n",dis[1]);return 0;}
		vis[u]=1;
		fp(v,1,n)if(!vis[v]){
			tmp[v]+=dis[u]*prod[v]*P[v][u];
			prod[v]*=1-P[v][u];
			dis[v]=tmp[v]/(1-prod[v]);
		}
	}
	return 1;
}

CF605E

原文：https://www.cnblogs.com/misaka10047/p/13266500.html