#P1339. P1339 [USACO09OCT] Heat Wave G
P1339 [USACO09OCT] Heat Wave G
P1339 [USACO09OCT] Heat Wave G
普及/提高- | 来源:USACO09OCT | 原题链接
题意
给定 个点、 条无向带权边与两个点 。求 到 的最短距离。注意:无向图建边要加两次。
输入格式
第一行四个正整数 。 接下来 行,每行三个正整数 ,表示一条连接 ,长为 的边。
输出格式
输出一行一个整数,表示答案。
输入输出样例
样例 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
数据范围
,,。
提示
考点:模板应用。易错点:无向边要加两次(正反各一条); 可能等于 的边界情况。