王老师的旅行问题

题目内容

题目描述

在某个国家有N个城市,被编号为0到n-1,城市之间由M个班次的列车连接,每个班次的列车连接两个城市并且只会走固定的线路和方向。现在王老师来到了这个国家旅游,他在城市0下飞机,想要以最快的速度赶往城市n-1参加一个活动,因此他拿到了所有列车的信息,包括列车的出发地和目的地还有单程所需的时间。忽略城市内的路程和候车的时间,王老师希望你帮忙找出一个方案使得他能够尽早的到达城市n-1.

输入描述

第一行两个整数N和M。

下面M行每行3个整数,分别代表一个班次的列车的出发地A、目的地B和所需时间T。

其中A,B<N≤2×104,M≤2×105,T≤104

输入保证城市0和城市n-1有直接或间接的列车线路连接,并且不存在出发地和目的地都相同的列车。

输出描述

第一行一个整数表示所需的最短时间。

第二行按顺序输出途径的每个城市编号,包括城市0和城市n-1,每个编号之间用“->”箭头隔开。

样例输入

5 8 0 1 5 0 3 4 0 4 10 1 2 7 1 3 10 2 4 2 3 2 3 4 3 12

样例输出

9 0->3->2->4

提示

提交评测
请登录后再操作

题目描述

王老师的旅行问题
1184
0
Level4
11
9
82%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在