最短路径问题

题目描述

给定一个包含 n (1 ≤ n ≤ 2500) 个点和 m (1 ≤ m ≤ 6200) 条边的无向图，求从点 s 到点 t 的最短路径。

输入格式

输入的第一行包含四个由空格隔开的整数 n、m、s 和 t。

接下来的 m 行，每行包含三个正整数 si、ti 和 wi (1 ≤ wi ≤ 10^9)，表示一条从点 si 到点 ti 长度为 wi 的边。注意这是一个无向图，所以每条边的两个方向都可以通行。

输出格式

输出一个整数表示从点 s 到点 t 的最短路径长度。数据保证至少存在一条道路。

样例

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

7

来源

一本通在线评测