图上极差 II
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
图上极差 II
友情提示：补题是一个好习惯，本题与图上极差 I 唯一的区别在于扩大了 和 的范围到 ，并且将时间限制改为 3000ms。此外，图上极差 I 的评测数据是本题评测数据的子集，占 。
题目描述
Orange正在学习图论算法，他将给定你一张 个点， 条边的带权无向图，现在他打算从 点走到 点，且要求最小化所经过边的极差。请你帮他求出最小的极差。
注意：你可以重复经过一条边多次！
经过边的极差定义为经过的最大边权与最小边权之差。
输入格式
第一行为4个整数 ，表示图的点数和边数，以及起点和终点。 接下来 行，每行3个整数 ，表示点 和 之间存在一条长度为 的边。
数据范围
数据保证图联通。
输出格式
输出一个整数，表示答案。
样例 #1
样例输入 #1
5 5 1 5
1 2 1
2 4 2
4 5 4
1 3 7
3 5 9
样例输出 #1
2
2026年沈阳师范大学团体程序设计天梯赛-校内选拔赛
- 状态
- 已结束
- 规则
- IOI
- 题目
- 15
- 开始于
- 2026-3-7 9:00
- 结束于
- 2026-3-7 12:00
- 持续时间
- 3 小时
- 主持人
-
Orange
- 参赛人数
- 40