#P11770. [2023年联测]走路
[2023年联测]走路
走路 (walk)
题目描述
EFZ 的校园可以抽象成一张个点条边的无向图,边带权。wygz 初始站在 号点,她想要去找站在 号点的 ix35。
wygz 不想走重复的边,但她觉得走重复的点是可以接受的。定义一条路径的权值是这条路径上边权的最大值与最小值的和。
对于每个 ,wygz 想知道以 为起点、 为终点的路径权值最小是多少。
输入格式
第一行, 两个正整数 。
接下来 行,每行三个整数,表示一条边连接两点,边权为。允许边权为0。
输出格式
共 行,对于 依次输出答案。若某点从点1不可达,对应输出 -1。
样例输入 1
3 3
1 2 2
1 3 1
2 3 1
样例输出 1
2
2
样例输入 2
7 10
1 2 2
1 2 8
2 3 3
3 4 5
3 5 4
4 5 4
6 5 7
6 4 4
1 7 6
6 7 9
样例输出 2
4
5
6
6
6
10
样例输入 3
4 4
1 2 2
3 2 0
2 4 3
4 3 1
样例输出 3
3
2
2
大样例
见下发文件,其中 walk .in/out 表示满足相应 Subtask 的限制
数据范围
保证 ,,。
| 子任务 | 上界 | 上界 | 特殊限制 | 分值 |
|---|---|---|---|---|
| 1 | 9 | |||
| 2 | 与点 1 相连的边权为 0 | 17 | ||
| 3 | 与点 1 相连的边权为 | 12 | ||
| 4 | 10 | 无重边 | 9 | |
| 5 | 20 | 6 | ||
| 6 | 2000 | 所有边满足 | ||
| 7 | 无 | 9 | ||
| 8 | 5000 | 8 | ||
| 9 | 依赖前面所有子任务 | 24 | ||