2356: 【基础】最短距离和路径问题(2047)

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：2

题目描述

有 lns="http://www.w3.org/1998/Math/MathML">� 个城市（编号为 lns="http://www.w3.org/1998/Math/MathML">1∼�），lns="http://www.w3.org/1998/Math/MathML">� 条道路（lns="http://www.w3.org/1998/Math/MathML">�<1000,�<10000)，每条道路有个长度（道路是双向的，两个方向都能走），请找到从起点 lns="http://www.w3.org/1998/Math/MathML">� 到终点 lns="http://www.w3.org/1998/Math/MathML">� 的最短距离和经过的城市名。

输入

第一行输入四个数，分别为 lns="http://www.w3.org/1998/Math/MathML">�，�，�，�。（lns="http://www.w3.org/1998/Math/MathML">�<1000,�<10000，1≤�,�≤�）

接下来 lns="http://www.w3.org/1998/Math/MathML">� 行，每行三个数 lns="http://www.w3.org/1998/Math/MathML">�，�，��� ，分别为两个城市名和距离。（lns="http://www.w3.org/1998/Math/MathML">1≤�,�≤�，1≤���≤50000

输出

每组输出占两行。

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

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

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

样例输入 复制 

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

样例输出 复制 

2
1 2 3

提示

来源/分类

提交提交记录统计露一手!