#P18930. [2026多校联测]航路防护

[2026多校联测]航路防护

航路防护

题目描述

风暴来临前,运输队要加固一些航路,保证物资仍能按时从站点 11 送到站点 nn。

航路网有 nn 个站点和 mm 条双向航路,站点编号为 11 至 nn。第 ii 条航路连接 ui,viu_i,v_i,通行时间为 wiw_i,加固它需要支付 cic_i。整个航路网连通,没有连接站点自身的航路。同一对站点之间可以有多条航路,它们分别加固、分别计算费用。

一次风暴最多损坏一条未加固的航路,也可能没有航路损坏。损坏的航路无法通行,已经加固的航路不会损坏。加固不会改变通行时间。

给定时间上限 BB,你要在风暴发生前选好加固方案。无论哪条未加固的航路损坏,也无论是否发生损坏,都必须存在一条从站点 11 到站点 nn 的路线,其通行时间之和不超过 BB。知道损坏情况后,可以改走其他路线,不要求所有情况下使用同一条路线。

请你求出满足要求的最小加固费用。如果即使加固全部航路也无法满足要求,输出 −1-1。

共有 qq 次询问,每次给出一个时间上限 BB。每次询问都从原来的航路网重新考虑,各次询问之间不保留加固结果。

输入格式

第一行三个整数 n,m,qn,m,q。

接下来 mm 行,每行四个整数 ui,vi,wi,ciu_i,v_i,w_i,c_i,描述第 ii 条航路。

接下来 qq 行,每行一个整数 BB,表示一次询问。

输出格式

输出 qq 行,每行一个整数,依次表示相应询问的最小加固费用,无解时为 −1-1。

样例 1 输入

3 3 3
1 2 1 5
2 3 1 7
1 3 4 2
1
2
4

样例 1 输出

-1
12
0

样例 1 解释

原图最短路长为 22,因此 B=1B=1 时无解。B=2B=2 时必须加固前两条航路,费用为 1212。B=4B=4 时无需加固:前两条中任意一条损坏,都可改走通行时间为 44 的直达航路。

样例 2 输入

3 2 3
1 2 2 3
2 3 2 8
3
4
10

样例 2 输出

-1
11
11

样例 2 解释

B=3B=3 时,即使没有航路损坏也无法按时到达。B=4B=4 和 B=10B=10 时,都必须加固唯一路线上的两条航路,费用为 1111。

样例 3

见下发文件中的 shelter/3.in 和 shelter/3.ans。这是一组较大的样例,题面中不展开。

数据范围与子任务

对于所有测试数据,保证:2≤n≤1000002\le n\le100000,n−1≤m≤200000n-1\le m\le200000,1≤q≤1000001\le q\le100000,1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i,1≤wi≤1091\le w_i\le10^9,0≤ci≤1090\le c_i\le10^9,0≤B≤10150\le B\le10^{15}。图连通。

本题共有四个子任务,各组独立计分。通过某组全部测试点,才能得到该组分数。

子任务 分值 额外约束
1 20 n≤60n\le60,m≤120m\le120,q≤60q\le60
2 航路网是一棵树
3 n≤1000n\le1000,m≤2000m\le2000,q≤10000q\le10000
4 40 无额外约束