Skip to content

1342: Shortest path

题目

题目描述

给一个 $n (1\leq n \leq 2500)$ 个点 $m(1\leq m\leq 6200)$ 条边的无向图,求 $s$ 到 $t$ 的最短路的长度。

数据保证,$s$ 出发可以到达 $t$。

Input

请从 stdin 读入。

第一行为四个正整数 $n, m, s, t$。 第二行起 $m$ 行,每行三个非负整数 $u_i, v_i, w_i (0 \leq w_i \leq 10 ^ 9)$,表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的无向边。

Output

请输出到 stdout 中。

输出一行一个整数,表示 $s$ 到 $t$ 的距离。

Sample Input

txt 4 4 1 4 1 2 999999999 2 3 1000000000 3 4 1000000000 1 2 1000000000

txt 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

Sample Output

txt 2999999999

txt 7

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!