Dwendwen的约会
Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
11.19%(15/134)
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