题目描述

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

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

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

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

输入格式

第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

输出格式

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

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论