9092:最短路

Time/Memory Limit:1000 MS/32768 K
Submitted: 533 Accepted: 325

 Problem Description

“水上之都”威尼斯水城是个美丽的地方,ax幻想着某天能够去那里旅游!
 
一天,ax想到一个问题:
威尼斯由许多n个小岛(由0到n-1编号)以及m座桥梁连成一体,桥梁可双向通行!假设ax在s号小岛上,要去t号小岛游玩!那么s到t的最短距离是多少!

 Input

本题目包含多组数据:
每组数据第一行包含两个正整数n和m(0<n<200,0<m<1000),分别代表现有小岛的数目和已修建桥梁的数目;
接下来是m行桥梁的信息,每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示小岛A和小岛B之间有一条长度为X的桥梁,桥梁可双向通行;
再接下一行有两个整数s,t(0<=s,t<n),分别代表起点和终点。

 Output

对于每组数据,请在一行里输出最短距离,如果不存在s到t的路径则输出"not found!"。

 Sample Input

3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2

 Sample Output

2
not found!

 Author

ax

 Recommend

zh