问题2190--最爱的城市

2190: 最爱的城市

时间限制: 1 Sec  内存限制: 128 MB
提交: 30  解决: 11
[提交] [状态] [讨论版] [命题人:]

题目描述

一天，小明捧着一本世界地图在看，突然他拿起笔，将他最爱的那些城市标记出来，并且随机的将这些城市中的某些城市用线段两两连接起来。
小明量出了每条线段的长度，现在他想知道在这些线段组成的图中任意两个城市之间的最短距离是多少。

输入

输入包含多组测试数据。每组：
第一行为两个正整数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，2，···，n，L≤20。

输出

对于每组输入，输出x市与y市之间的最短距离，如果x市与y市之间非连通，则输出“No path”。

样例输入 Copy 

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

样例输出 Copy 

3

来源/分类

最短路径 Bellman_Ford算法 Dijkstra算法 SPFA算法 Floyd算法 深度优先搜索算法 
[提交] [状态]