问题 4331 --校园的路径

4331: 校园的路径

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

题目描述

       bnuzh正在修路,有些地方走不通,需要绕地方行走。kai哥跟东哥说:“从海华到综合再到校名石比较近。”,东哥说:“明明是从海华到UIC再到校名石比较近。”他们两个在争论着这个问题,现在想请聪明的你帮他们写个程序帮他们解决这个问题。

输入

输入4个数,s,e,n,m,为别为起点,目标点,总的建筑个数,总的路径数。 (0 < n < 1000,0 <= m < 50000, 1 <= s,e <= n)

接下来输入m条路径,x,y,d,表示从x号建筑到y号建筑的距离为d。( 1 <= x,y <= n, x != y,0 < d <= 100)。

路径是双向的,即从x到y的距离等于从y 到x的距离。

s,e,n,m为0,0,0,0的时候结束。

输出

s到e的最短的路径长度。若无法到达,则输出-1。

样例输入

1 5 5 5<br/>1 2 1<br/>2 3 2<br/>3 4 3<br/>4 5 4<br/>1 5 9<br/>0 0 0 0

样例输出

9<br/>

来源

[提交][状态]