2047 - 最短距离和路径问题

题目描述

nn 个城市(编号为 1n1 \sim n),mm 条道路(n<1000,m<10000n < 1000, m < 10000),每条道路有个长度(道路是双向的,两个方向都能走),请找到从起点 ss 到终点 tt 的最短距离和经过的城市名。

输入

第一行输入四个数,分别为 nmstn,m,s,t。(n<1000,m<100001s,tnn < 1000, m < 10000,1≤s,t≤n

接下来 mm 行,每行三个数 xylenx,y,len ,分别为两个城市名和距离。(1x,yn1len500001≤x,y≤n,1≤len≤50000

输出

每组输出占两行。

第一行输出起点到终点的最短距离。

第二行输出最短路径上经过的城市名,如果有多条最短路径,输出字典序最小的那条。若不存在从起点到终点的路径,则输出can't arrive

请注意:本题两个相同的城市之间可能存在多条路径。

样例

输入
复制

3 3 1 3
1 3 3
1 2 1
2 3 1

输出
复制

2
1 2 3

输入
复制

4 3 1 4
1 2 3
1 2 1
2 3 1

输出
复制

can't arrive
来源

图论

标签
题目参数
时间限制 1 秒
内存限制 32 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题