Dwendwen的约会

Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/13)
Description:

Dwendwen和女朋友去游乐园约会,因为天气太热了,他们想快点到达终点,身为同济博士的Dwendwen瞬间计算出了所有的最短路径,同时,每个游乐项目都有一个受欢迎值,Dwendwen女朋友希望在最短路中找出受欢迎值之和最大的那条。

Input:

第一行输入4个正整数n,m,st,ed,分别代表游乐项目的个数、边的条数、Dwendwen他们的起点编号和终点编号(编号从0开始,1<=n<=1000, 1<=m<=400000)
第二行输入n个正整数,表示每个游乐项目的受欢迎值w(w<=1000)。
接下来m行,每行输入3个正整数x,y,v,表示游乐项目x到游乐项目y的距离(v<=1000)。

Output:

从起点到终点最短路的条数和受欢迎值之和的最大值。

Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4

Submit