#3052. huhe跑马拉松

huhe跑马拉松

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

huhe是一位城市马拉松爱好者,可是有一天他跑得太远了,回去要很长的一段时间。他要从第1个路口跑回第n个路口。他找到了你,求你帮他找到最快的路径,使他可以最快的回到家。

Format

Input

输入共m+1行,第一行包括三个数,n,m,即路口个数,路径个数。 接下来m行,每行三个整数,x,y,v,即从第x个路口到第y个路口要花v的时间(每条路是单向的)。

Output

输出只有一行,即所需最短时间。

Samples

5 5
1 2 1
2 3 2
3 4 2
2 4 5
4 5 1
6

Tips

对于100%的数据,2<=n<=10000,1<=m<=20000,0<=v<=100,000;

中心团队A团——图论4(Bellman Ford & SPFA)

未参加
状态
已结束
规则
IOI
题目
5
开始于
2023-12-2 15:15
结束于
2023-12-6 1:15
持续时间
82 小时
主持人
参赛人数
21