A70741. 最短距离和路径问题
编程题
基础
知识点
题目描述
有 n 个城市（编号为 1 \sim n），m 条道路（n < 1000, m < 10000)，每条道路有个长度（道路是双向的，两个方向都能走），请找到从起点 s 到终点 t 的最短距离和经过的城市名。
输入格式
第一行输入四个数，分别为 n,m,s,t。（n < 1000, m < 10000，1≤s,t≤n）
接下来 m 行，每行三个数 x,y,len ，分别为两个城市名和距离。（1≤x,y≤n，1≤len≤50000）
输出格式
每组输出占两行。
第一行输出起点到终点的最短距离。
第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条。若不存在从起点到终点的路径，则输出can't arrive。
请注意：本题两个相同的城市之间可能存在多条路径。
输入输出样例
输入 #1
3 3 1 3 1 3 3 1 2 1 2 3 1
输出 #1
2 1 2 3
输入 #2
4 3 1 4 1 2 3 1 2 1 2 3 1
输出 #2
can't arrive
说明/提示
## 思路
「最短距离和路径问题」先建图再遍历或求特殊路径。
## 步骤
1. 读入点数边数并建邻接表。
2. 按题意 DFS/BFS 或求最短路、欧拉路。
3. 输出路径或距离。
「最短距离和路径问题」先建图再遍历或求特殊路径。
## 步骤
1. 读入点数边数并建邻接表。
2. 按题意 DFS/BFS 或求最短路、欧拉路。
3. 输出路径或距离。