2044: 【入门】城市之间的最短路

时间限制: 1 Sec  内存限制: 32 MB
提交: 0  解决: 0  金币: 1
[提交][状态]

题目描述

小丁同学准备去A国旅游,他买了一张A国的地图,地图标出了A国著名的n个旅游热门城市,并标注了这n个城市之间有m条路线相连以及每条路线的长度。

请你编程帮助小丁求出其中两个城市之间的最短距离。


输入

输入第一行为两个正整数n(n<=10)和m(m<=n*(n-1)/2),n表示城市个数,m表示线段个数。
接下来m行,每行输入三个整数a,b和l,表示a市与b市之间存在一条线段,线段长度为l。(a与b不同,且本题的数据中两个城市之间最多只有一条路)
每组最后一行输入两个整数x和y,表示问题:x市与y市之间的最短距离是多少。(x与y不同)
城市标号为1~n,l<=20。

输出

输出x市与y市之间的最短距离,如果x市与y市之间非连通,则输出“No path”。

样例输入复制

4 4
1 2 4
1 3 1
1 4 1
2 3 1
2 4

样例输出复制

3

来源

[提交][状态]