4.2模拟赛 wormhole(期望DP Dijkstra)

$\color{white}{orzmjt又切题了...}$

$Description$

给定一张有向图，每条边在每一时刻有$p_i$的概率存在。求最优策略下从$1$走到$n$最少需要多长时间。

$n,m\leq10^5$。

$Solution$

在八十中做过一道类似的题...（我都想不起那题是哪的了还是mjt想起来的orz）

令$f_x$表示$x$点到$n$点最少的期望花费时间。对比样例解释可以猜出能够想到，假设最优解中转移到$x$的点是$v_1,v_2,...,v_k$，且这些点是按$f_{v_i}$从小到大排好序的，那么有$$f_x=p_{(x,v_1)}f_{v_1}+(1-p_{(x,v1)})p_{(x,v2)}f_{v_2}+...+\prod_{i=1}^k(1-p_{(x,v_i)})f_x$$

用$Dijkstra$转移就可以了（每次出队的一定已经是最优的$f_v$，且是从小到大的。如果$f_v$能使$f_x$变小，就要$v$，否则不管）。

考试的时候没判$vis$，有双向边然后$f[x]$重复转移了丢了一堆分mdzz。。

#include <queue>

#include <cstdio>

#include <cctype>

#include <algorithm>

#define mp std::make_pair

#define pr std::pair<double,int>

//#define gc() getchar()

#define MAXIN 300000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1e5+5;

int Enum,H[N],nxt[N],to[N];

double P[N];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-48,c=gc());

	return now;

}

inline void AE(double w,int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, P[Enum]=w/100.0;

}

void Dijkstra(int n,int m)

{

	static double f[N],sp[N];

	static bool vis[N];

	std::priority_queue<pr> q;

	f[n]=0, q.push(mp(0,n));

	for(int i=1; i<=n; ++i) sp[i]=1;

	while(!q.empty())

	{

		int x=q.top().second; q.pop();

		if(vis[x]) continue;

		vis[x]=1;

		if(x!=n) f[x]=(f[x]+1)/(1-sp[x]);

		for(int i=H[x]; i; i=nxt[i])

		{

			int v=to[i]; if(vis[v]) continue;

			double tmp=(f[v]+f[x]*sp[v]*P[i])/(1-sp[v]*(1-P[i]));

			if(sp[v]==1||(f[v]+1)/(1-sp[v])>tmp) f[v]+=f[x]*sp[v]*P[i], sp[v]*=(1-P[i]), q.push(mp(-(f[v]+1)/(1-sp[v]),v));

		}

	}

	printf("%.3f\n",f[1]);

}

int main()

{

	freopen("wormhole.in","r",stdin);

	freopen("wormhole.out","w",stdout);

	int n=read(),m=read();

	for(int i=1; i<=m; ++i) AE(read(),read(),read());

	Dijkstra(n,m);

	return 0;

}

巴特西

4.2模拟赛 wormhole(期望DP Dijkstra)

\(Description\)

\(Solution\)

最新文章

热门文章