#P1339. [USACO09OCT] Heat Wave G

    ID: 383 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论最短路USACO福建省历届夏令营2009

[USACO09OCT] Heat Wave G

题目描述

有一个 nn 个点 mm 条边的无向图,请求出从 sstt 的最短路长度。

输入格式

第一行四个正整数 n,m,s,tn,m,s,t。 接下来 mm 行,每行三个正整数 u,v,wu,v,w,表示一条连接 u,vu,v,长为 ww 的边。

输出格式

输出一行一个整数,表示答案。

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

提示

【数据范围】
对于 100%100\% 的数据,1n25001\le n \le 25001m62001\le m \le 62001w10001\le w \le 1000

【样例说明】
56145 \to 6 \to 1 \to 4 为最短路,长度为 3+1+3=73+1+3 = 7