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了，可以的话，请您参考添加页面，与大家一起分享你的题解！