拓扑排序+数学+DP【p1685】游览

Description

顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！

你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。

我们把桃花岛抽象成了一个图，共n个点代表路的相交处，m条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路线。两条路线被认为是不同的当且仅当它们所经过的路不完全相同。

你的任务是：把所有不同的路线游览完一共要花多少时间？

Input

第1行为5个整数：n、m、s、t、t0，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从1到n）和你乘船从岛东头到西头一次的时间。

以下m行，每行3个整数：x、y、t，表示从点x到点y有一条行走耗时为t的路。

每一行的多个数据之间用一个空格隔开，且：2<=n<=10000; 1<=m<=50000;t<=10000;t0<=10000

Output

假设总耗时为total,则输出total mod 10000的值（total对10000取余）。

很明显,此图为一个\(DAG\)，如何搞呢?拓扑排序!

但这样依旧无法搞,考虑到统计方案数了,我们考虑\(DP\)

设\(f[i]\)代表到达\(i\)的总的耗时.\(g[i]\)代表到达\(i\)的方案数.

根据乘法原理与加法原理，很容易写出状态转移方程

\(u\)代表当前点,\(v\)代表当前边所连的点.(应该不是很难理解,就不解释了)

\[f[u]+=f[v]+g[u]*edge[i].w \\g[u]+=g[v]
\]

真不知道这题为什么是紫题

代码

#include<cstdio>

#include<cctype>

#define R register

#define N 100008

#define mod 10000

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,m,s,t,t0,stk[N],top;

int head[N],tot,ins[N],f[N],g[N];

struct cod{int u,v,w;}edge[N<<2];

inline void add(int x,int y,int z)

{

	edge[++tot].u=head[x];

	edge[tot].v=y;

	edge[tot].w=z;

	head[x]=tot;

}

inline void topsort()

{

	for(R int i=1;i<=n;i++)

		if(!ins[i])stk[++top]=i,g[i]=1;

	while(top)

	{

		int u=stk[top--];

		for(R int i=head[u];i;i=edge[i].u)

		{

			ins[edge[i].v]--;

			(f[edge[i].v]+=f[u]+g[u]*edge[i].w)%=mod;

			(g[edge[i].v]+=g[u])%=mod;

			if(!ins[edge[i].v])stk[++top]=edge[i].v;

		}

	}

}

int main()

{

	in(n),in(m),in(s),in(t),in(t0);

	for(R int i=1,x,y,z;i<=m;i++)

	{

		in(x),in(y),in(z);

		if(x==y)continue;

		add(x,y,z);

		ins[y]++;

	}

	topsort();

	printf("%d",(f[t]%mod+(g[t]-1)*t0)%mod);

}

巴特西

拓扑排序+数学+DP【p1685】游览

Description

Input

Output

最新文章

热门文章