#P18930. [2026多校联测]航路防护
[2026多校联测]航路防护
航路防护
题目描述
风暴来临前,运输队要加固一些航路,保证物资仍能按时从站点 送到站点 。
航路网有 个站点和 条双向航路,站点编号为 至 。第 条航路连接 ,通行时间为 ,加固它需要支付 。整个航路网连通,没有连接站点自身的航路。同一对站点之间可以有多条航路,它们分别加固、分别计算费用。
一次风暴最多损坏一条未加固的航路,也可能没有航路损坏。损坏的航路无法通行,已经加固的航路不会损坏。加固不会改变通行时间。
给定时间上限 ,你要在风暴发生前选好加固方案。无论哪条未加固的航路损坏,也无论是否发生损坏,都必须存在一条从站点 到站点 的路线,其通行时间之和不超过 。知道损坏情况后,可以改走其他路线,不要求所有情况下使用同一条路线。
请你求出满足要求的最小加固费用。如果即使加固全部航路也无法满足要求,输出 。
共有 次询问,每次给出一个时间上限 。每次询问都从原来的航路网重新考虑,各次询问之间不保留加固结果。
输入格式
第一行三个整数 。
接下来 行,每行四个整数 ,描述第 条航路。
接下来 行,每行一个整数 ,表示一次询问。
输出格式
输出 行,每行一个整数,依次表示相应询问的最小加固费用,无解时为 。
样例 1 输入
3 3 3
1 2 1 5
2 3 1 7
1 3 4 2
1
2
4
样例 1 输出
-1
12
0
样例 1 解释
原图最短路长为 ,因此 时无解。 时必须加固前两条航路,费用为 。 时无需加固:前两条中任意一条损坏,都可改走通行时间为 的直达航路。
样例 2 输入
3 2 3
1 2 2 3
2 3 2 8
3
4
10
样例 2 输出
-1
11
11
样例 2 解释
时,即使没有航路损坏也无法按时到达。 和 时,都必须加固唯一路线上的两条航路,费用为 。
样例 3
见下发文件中的 shelter/3.in 和 shelter/3.ans。这是一组较大的样例,题面中不展开。
数据范围与子任务
对于所有测试数据,保证:,,,,,,,。图连通。
本题共有四个子任务,各组独立计分。通过某组全部测试点,才能得到该组分数。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 20 | ,, |
| 2 | 航路网是一棵树 | |
| 3 | ,, | |
| 4 | 40 | 无额外约束 |