#P18896. [2026多校联测]迷路的送货车

[2026多校联测]迷路的送货车

题目描述

一辆自动送货车负责为夜市运送货物。车辆的导航可能从允许通行的道路中任意选择下一条道路。司机可以付费临时屏蔽道路,也可以在行程中使用一次人工接管,希望在最坏情况下仍能以尽可能低的费用到达仓库。

路网有 nn 个路口,编号为 1,2,…,n1,2,\ldots,n,以及 mm 条有向道路。仓库在路口 nn。第 ee 条道路从 ueu_e 通向 vev_e,通行费用为 wew_e,临时屏蔽费用为 cec_e。不同道路可能连接相同的两个路口,但它们仍分别计费、分别选择。

车辆每次准备从非仓库路口 uu 离开时(包括出发时),司机可以选择以下方式之一。

  1. 自动驾驶:选择 uu 的若干条出边临时屏蔽,可以一条也不屏蔽。支付被屏蔽道路的费用之和,并至少留下一个未屏蔽的出边。随后,导航从留下的出边中任意选择一条,车辆沿该道路行驶,并支付它的通行费用。临时屏蔽仅对这次离开有效,之后立即失效。
  2. 人工接管:直接选择 uu 的一个出边行驶,只支付该道路的通行费用,不支付屏蔽费用。整个行程最多使用一次人工接管,也可以不用。

司机可以根据已经发生的行程作决定。使用自动驾驶时,司机先决定屏蔽哪些道路,导航再从未屏蔽道路中选择。再次访问某个路口时,仍按上述规则重新支付费用;人工接管机会不会恢复。首次到达仓库后立即结束行程,不再支付任何费用。如果某种驾驶策略可能导致永远无法到达仓库,或者停在没有出边的非仓库路口,就认为它不能保证完成配送。

对每个出发路口,求最小的非负整数 FF,使司机存在一种策略,无论导航如何选择,都能在有限次行驶后到达仓库,且屏蔽费与通行费的总和不超过 FF。各个起点分别计算,开始时都拥有一次接管机会;不存在这样的 FF 时,答案为 −1-1。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,第 ee 行四个整数 ue,ve,we,ceu_e,v_e,w_e,c_e,含义如题目描述。

输出格式

输出一行 nn 个整数,第 ii 个整数表示从路口 ii 出发的答案。仓库自身的答案为 00,费用不取模。

样例 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 解释

从路口 22 出发时,可以立即人工接管,沿道路 2→42\to4 到达仓库,费用为 44。

从路口 11 出发时,可以先支付 22 屏蔽通向路口 33 的道路,自动行驶到路口 22,支付通行费 11;再人工接管行驶到仓库,支付 44。总费用为 77。人工接管机会留到路口 22 比立即使用更合适。

样例 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,21,2 出发,只能在二者之间行驶,无法到达仓库。路口 33 可以人工接管直接到达仓库,费用为 77;从路口 44 出发,可以先自动行驶到路口 33,再接管,总费用为 99。

子任务

对于所有测试数据,保证:2≤n≤2000002\le n\le200000,0≤m≤4000000\le m\le400000,1≤ue,ve≤n1\le u_e,v_e\le n,ue≠veu_e\ne v_e,1≤we≤1091\le w_e\le10^9,0≤ce≤1090\le c_e\le10^9。图可能有环,也可能有无法到达仓库的路口。

各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。

子任务 分值 额外约束
1 20 n≤8,m≤16n\le8,m\le16,每个路口的出边不超过 55 条(重边按条计数)
2 n≤2500,m≤5000n\le2500,m\le5000,所有道路满足 ue<veu_e<v_e
3 所有道路满足 ce=0c_e=0
4 40 无额外约束