分数: 475 点
问题陈述
在Atcoder的国家里,有 N 城市编号 1 to N,和 M 编号为 1 to M。 火车 i 从市区出发 A_i 时间 S_i 并到达城市 B_i 时间 T_i.
给定一个正整数 X_1,找到设置非负整数的方法 X_2,\ldots,X_M 满足以下条件,其最小可能值为 X_2+\ldots+X_M.
- 条件:对于所有对 (i,j) 满意 1 \leq i,j \leq M,如果 B_i=A_j 和 T_i \leq S_j,然后 T_i+X_i \leq S_j+X_j.
- 也就是说,对于任意一对原本可以换乘的列车,即使延迟每趟列车的出发和到达时间,仍然可以换乘 i by X_i.
可以证明,这样设置 X_2,\ldots,X_M 的最小可能值为 X_2+\ldots+X_M 是独一无二的。
约束
- 2 \leq N \leq 2\times 10^5
- 2 \leq M \leq 2\times 10^5
- 1 \leq A_i,B_i \leq N
- A_i \neq B_i
- 0 \leq S_i < T_i \leq 10^9
- 1 \leq X_1 \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X_1 A_1 B_1 S_1 T_1 \vdots A_M B_M S_M T_M
输出
打印 X_2,\ldots,X_M 满足具有最小可能总和的条件,按该顺序,用空格分隔。
示例输入 1
3 6 15 1 2 10 20 1 2 20 30 2 3 25 40 2 3 35 50 3 1 15 30 3 1 45 60
示例输出 1
0 10 0 0 5
火车到站 1 来自城市 1 to 2 延迟 15 变成时间 35.
允许从火车转乘 1 to 3 在城市 2, 火车出发 3 延迟 10,使其按时出发 35 并按时到达 50.
此外,允许从火车转乘 3 to 6 在城市 3, 火车出发 6 延迟 5,使其按时出发 50.
其他列车可以立即运行,同时仍允许在原本可换乘的列车之间进行换乘,因此 (X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) 满足条件。
而且,不存在满足条件的和更小的解,所以这就是答案。
示例输入 2
10 9 100 1 10 0 1 10 2 1 100 10 3 1 100 10 4 1 100 10 5 1 100 10 6 1 100 10 7 1 100 10 8 1 100 10 9 1 100
示例输出 2
100 100 100 100 100 100 100 100
示例输入 3
4 4 10 1 2 0 1 1 2 0 10 2 3 100 200 2 4 100 200
示例输出 3
0 0 0