Dotcpp  >  编程题库  >  梦之国
题目 2632:

梦之国

时间限制: 2s 内存限制: 192MB 提交: 37 解决: 5

题目描述

在刚刚,你已经选好的梦想。

但是,总有许多你还需要学习的知识。

你便迈向了梦之国,因为那里充满了知识和大佬。

orz


你总是想要在电脑上展现自己,于是便开始编写此题。

从你的出发地到梦之国途经 n 个驿站(包括出发地和梦之国),每一个驿站都有一个编号,我们将出发地的编号记为 f ,梦之国的编号记为 d 。驿站间以 m 条路链接,都是双向通行的。

每一条道路拥有一个不是来自平行宇宙的长度 w(即 w 为正整数)

你为了更快学到知识,你需要更快到达梦之国。

你需要找出从 f 到 d 的最短路径的长度。

输入格式

共 m + 1 行。

第一行:四个整数 n, m, f, d,具体含义见上文。

接下来的 m 行:每行三个正整数 u, v, w 表示从 u 到 v(同时也是 v 到 u ) 有一条路,且长度为 w 。

输出格式

共 1 行

一个正整数,表示 f 到 d 的最短路径的长度。

样例输入

10 20 9 4
5 6 308
8 10 696
4 2 569
8 6 471
1 2 874
5 3 130
4 5 804
8 9 89
10 4 717
10 9 41
7 6 998
1 6 639
7 9 650
7 8 339
3 1 597
9 1 622
7 10 2
5 1 4
1 4 372
1 10 163

样例输出

576

提示

对于 100% 的数据:1 ≤ n ≤ 2500 , 1 ≤ m ≤ 6200 , 1 ≤ wi ≤ 109 并保证其他数据均在 [ -231, 231 - 1](也就是int) 范围内。
标签