#P17822. [Ontak2022]BIA
[Ontak2022]BIA
题目描述
有 座山峰和 条双向山路。第 条山路连接 ,难度为 ,类型为 : 表示滑雪山路, 表示射击山路。
一条训练路线从某个山峰 出发,只沿射击山路到达另一个山峰 ,然后只沿滑雪山路返回 ,要求 。
路线费用等于所用射击山路的最大难度,加上所用滑雪山路的最大难度。求最小费用,或判断不存在这样的路线。
输入格式
第一行两个整数 。接下来 行,每行四个整数 。
输出格式
输出最小费用;不存在合法路线则输出 -1。
数据范围
,;,;;。题面不保证无重边或图连通。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | n≤500,m≤10000 | 7 |
| 2 | n≤6000 | 13 |
| 3 | n≤50000 | 29 |
| 4 | 所有滑雪山路难度为1 | 19 |
| 5 | 无额外限制 | 32 |
样例 1
输入:
6 8
5 2 4 1
1 3 2 1
2 6 2 0
4 3 10 1
4 1 3 1
6 3 4 0
4 5 1 0
6 4 5 1
输出:
9
样例 2
输入:
5 5
3 1 1 0
4 3 1 0
1 4 1 0
5 1 4 1
2 1 3 1
输出:
-1