#P18896. [2026多校联测]迷路的送货车
[2026多校联测]迷路的送货车
题目描述
一辆自动送货车负责为夜市运送货物。车辆的导航可能从允许通行的道路中任意选择下一条道路。司机可以付费临时屏蔽道路,也可以在行程中使用一次人工接管,希望在最坏情况下仍能以尽可能低的费用到达仓库。
路网有 个路口,编号为 ,以及 条有向道路。仓库在路口 。第 条道路从 通向 ,通行费用为 ,临时屏蔽费用为 。不同道路可能连接相同的两个路口,但它们仍分别计费、分别选择。
车辆每次准备从非仓库路口 离开时(包括出发时),司机可以选择以下方式之一。
- 自动驾驶:选择 的若干条出边临时屏蔽,可以一条也不屏蔽。支付被屏蔽道路的费用之和,并至少留下一个未屏蔽的出边。随后,导航从留下的出边中任意选择一条,车辆沿该道路行驶,并支付它的通行费用。临时屏蔽仅对这次离开有效,之后立即失效。
- 人工接管:直接选择 的一个出边行驶,只支付该道路的通行费用,不支付屏蔽费用。整个行程最多使用一次人工接管,也可以不用。
司机可以根据已经发生的行程作决定。使用自动驾驶时,司机先决定屏蔽哪些道路,导航再从未屏蔽道路中选择。再次访问某个路口时,仍按上述规则重新支付费用;人工接管机会不会恢复。首次到达仓库后立即结束行程,不再支付任何费用。如果某种驾驶策略可能导致永远无法到达仓库,或者停在没有出边的非仓库路口,就认为它不能保证完成配送。
对每个出发路口,求最小的非负整数 ,使司机存在一种策略,无论导航如何选择,都能在有限次行驶后到达仓库,且屏蔽费与通行费的总和不超过 。各个起点分别计算,开始时都拥有一次接管机会;不存在这样的 时,答案为 。
输入格式
第一行两个整数 。
接下来 行,第 行四个整数 ,含义如题目描述。
输出格式
输出一行 个整数,第 个整数表示从路口 出发的答案。仓库自身的答案为 ,费用不取模。
样例 1 输入
4 5
1 2 1 9
1 3 1 2
2 4 4 0
2 3 1 8
3 4 10 1
样例 1 输出
7 4 10 0
样例 1 解释
从路口 出发时,可以立即人工接管,沿道路 到达仓库,费用为 。
从路口 出发时,可以先支付 屏蔽通向路口 的道路,自动行驶到路口 ,支付通行费 ;再人工接管行驶到仓库,支付 。总费用为 。人工接管机会留到路口 比立即使用更合适。
样例 2 输入
5 5
1 2 2 3
2 1 1 4
3 5 7 0
3 4 1 100
4 3 2 0
样例 2 输出
-1 -1 7 9 0
样例 2 解释
从路口 出发,只能在二者之间行驶,无法到达仓库。路口 可以人工接管直接到达仓库,费用为 ;从路口 出发,可以先自动行驶到路口 ,再接管,总费用为 。
子任务
对于所有测试数据,保证:,,,,,。图可能有环,也可能有无法到达仓库的路口。
各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 20 | ,每个路口的出边不超过 条(重边按条计数) |
| 2 | ,所有道路满足 | |
| 3 | 所有道路满足 | |
| 4 | 40 | 无额外约束 |