问题 P: 最短路径

传统题
1.000s 时间限制
128MB 内存限制
1 提交
0 解决

【题目描述】
有n个城市m条道路(n<1000, m<10000),每条道路有个长度,请找到从起点s到终点t的最短距离和经过的城市名。
【输入】

输入包含多组测试数据。

每组第一行输入四个数,分别为n,m,s,t。

接下来m行,每行三个数,分别为两个城市名和距离

【输出】

每组输出占两行。

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

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

【样例输入】复制
3 3 1 3
1 3 3
1 2 1
2 3 1
【样例输出】 复制
2
1 2 3