#P1339. P1339 [USACO09OCT] Heat Wave G

P1339 [USACO09OCT] Heat Wave G

P1339 [USACO09OCT] Heat Wave G

普及/提高- | 来源:USACO09OCT | 原题链接

题意

给定 nn 个点、mm 条无向带权边与两个点 s,ts,t。求 ss 到 tt 的最短距离。注意:无向图建边要加两次。

输入格式

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

输出格式

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

输入输出样例

样例 1 输入

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

样例 1 输出

7

数据范围

1≤n≤25001\le n\le 2500,1≤m≤62001\le m\le 6200,1≤w≤10001\le w\le 1000。

提示

考点:模板应用。易错点:无向边要加两次(正反各一条);ss 可能等于 tt 的边界情况。

二、建图技巧

蜀ICP备2025119001号-1