问题2604--锻炼(exercise)

2604: 锻炼(exercise)

时间限制: 2 Sec  内存限制: 512 MB
提交: 24  解决: 13
[提交] [状态] [讨论版] [命题人:]

题目描述

小A作为一个游戏高手,但是平日里却缺乏一些必要的锻炼,而为了锻炼的积极性,它号召了n个一起玩游戏的朋友陪他一起锻炼。
他们准备在一张n个点m条边的无向连通图中进行他们的锻炼,第i个人的目标是从第1个点跑到第i个点,因为他们并不是很想锻炼,所以他们会选择最短的道路跑到目的地。
但是第二天,他们惊奇地发现所有边竟然都增长了1米,在接下来的时间里,他们发现每一天每条边都增长了1米,所以他们想要知道,在计划的T天里,他们总共要跑的距离之和(如果从1到达不了i,第i个人就不用跑)。 

输入

三个整数n,m,T表示图中节点个数,边数,总共的天数。
接下来m行,每行三个整数Xi,Yi,Di表示Xi与Yi之间有一条长度为Di米的边。

输出

一个整数ans,表示在T天里,所有人跑的距离之和,答案要对(1e9+7)取模。

样例输入 Copy

2 1 597855229 
1 2 1

样例输出 Copy

67096006

提示

样例输入2:
5 6 0
1 2 1
2 3 2
1 5 1
1 3 2
1 4 4
3 4 1
样例输出2:
7
对于30%的数据,n≤50,T≤100。
对于60%的数据,n≤50。
对于100%的数据,n≤2500,m≤5000, 0≤T≤1e9,Di≤800000。
【后记】
什么?你问我小A的锻炼效果?
作为游戏中的第一人,他当然也是要在这次锻炼里当做那个终点为1号节点的人啦。
训练效果肯定是很显著的啦。

来源/分类