← 返回题目列表

AtCoder · abc368_e

H. 火车晚点

中文机器翻译题面 查看原题

分数: 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