Intergalaxy Trips CodeForces - 605E (期望,dijkstra)

大意: 给定矩阵$p$, $p_{i,j}$表示每一秒点$i$到点$j$有一条边的概率, 每秒钟可以走一条边, 或者停留在原地, 求最优决策下从$1$到$n$的期望用时.

$f_x$为从$x$到$n$的期望用时, 每次肯定尽量选取$f$值小的后继走

假设每个点按$f$值排序后的序列为$a_1,a_2,...,x$, 有

$$f_x=1+f_1p_{x,a_1}+f_2p_{x,a_2}(1-p_{x,a_1})+...+f_xp_{x,x}\prod(1-p_{x,a_i})$$

$$f_x=\frac{1+\sum\limits_{i}f_{i}p_{x,i}\prod\limits_{j=1}^{i-1}(1-p_{x,a_j})}{1-\prod\limits_{i}(1-p_{x,a_i})}$$

$dijkstra$求出从$n$到$1$的最短路即可. $a_i$维护分子, $b_i$维护分母.

#include <iostream>

#include <algorithm>

#include <cstdio>

#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

const int N = 1e3+10;

int n,vis[N];

double a[N],b[N],p[N][N];

int main() {

	scanf("%d", &n);

	REP(i,1,n) REP(j,1,n) {

		int t;

		scanf("%d", &t);

		p[i][j] = t/100.;

	}

	REP(i,1,n-1) a[i]=b[i]=1;

	REP(i,1,n) {

		double mi = 1e18;

		int id = 0;

		REP(j,1,n) if (!vis[j]&&b[j]<1) {

			double f = a[j]/(1-b[j]);

			if (mi>f) mi=f,id=j;

		}

		if (id==1) return printf("%.10lf\n",mi),0;

		vis[id] = 1;

		REP(j,1,n) if (!vis[j]) {

			a[j]+=b[j]*p[j][id]*mi;

			b[j]*=1-p[j][id];

		}

	}

}

巴特西

Intergalaxy Trips CodeForces - 605E (期望,dijkstra)

最新文章

热门文章