同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1612_单源最短路

2022-5-16 18:17| 发布者: Hocassian| 查看: 41| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950441293299-Problem List-采集的数据-后羿采集器.html

Pro.ID

1612

Title

单源最短路

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1612

AC

Submit

Ratio

21.88%

时间&空间限制

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

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

输入

第一行四个由空格隔开的整数 n 、m 、s 、t 。之后的 m 行，每行三个正整数 s_i 、t_i 、w_i ( 1 ≤ w_i ≤ 10⁹) ，表示一条从 s_i 到 t_i 长度为 w_i 的边。

输出

Description

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

Input

Output

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

Sample Input

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

样例输入