A70742. 城市之间的最短路
编程题
入门
知识点
题目描述
小丁同学准备去A国旅游，他买了一张A国的地图，地图标出了A国著名的 n 个旅游热门城市，并标注了这 n 个城市之间有 m 条双向路线相连以及每条双向路线的长度。
请你编程帮助小丁求出其中两个城市之间的最短距离。
输入格式
输入第一行为两个正整数 n（n \le 10）和 m（m \le n \times (n-1)/2），n 表示城市个数，m 表示线段个数。
接下来 m 行，每行输入三个整数 a,b 和 l ，表示 a 市与 b 市之间存在一条线段，线段长度为 l 。（ a 与 b 不同，且本题的数据中两个城市之间最多只有一条路）
每组最后一行输入两个整数 x 和 y ，表示问题：x 市与 y 市之间的最短距离是多少。（x 与 y 不同）
城市标号为 1 \sim n， 1 \le l \le 20 。
输出格式
输出 x 市与 y 市之间的最短距离，如果 x 市与 y 市之间非连通，则输出 No path。
输入输出样例
输入 #1
4 4 1 2 4 1 3 1 1 4 1 2 3 1 2 4
输出 #1
3
说明/提示
## 思路
「城市之间的最短路」先建图再遍历或求特殊路径。
## 步骤
1. 读入点数边数并建邻接表。
2. 按题意 DFS/BFS 或求最短路、欧拉路。
3. 输出路径或距离。
「城市之间的最短路」先建图再遍历或求特殊路径。
## 步骤
1. 读入点数边数并建邻接表。
2. 按题意 DFS/BFS 或求最短路、欧拉路。
3. 输出路径或距离。