问题 B: 【基础】最短距离和路径问题

内存限制:32 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:43 解决:14

题目描述

有n个城市(编号为1~n),m条道路(n<1000, m<10000),每条道路有个长度,请找到从起点s到终点t的最短距离和经过的城市名。

输入

第一行输入四个数,分别为n,m,s,t。(n<1000, m<10000,1≤s,tn)
接下来m行,每行三个数x,y,len,分别为两个城市名和距离。(1≤x,yn,1len50000)

输出

每组输出占两行。
第一行输出起点到终点的最短距离。
第二行输出最短路径上经过的城市名,如果有多条最短路径,输出字典序最小的那条。若不存在从起点到终点的路径,则输出“can't arrive”。
请注意:本题两个相同的城市之间可能存在多条路径。

样例输入 复制

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

样例输出 复制

2
1 2 3