AT_abc368_e [ABC368E] Train Delay

题目描述

Atcoder 国有 $1$ 到 $N$ 编号的 $N$ 个城市，以及 $1$ 到 $M$ 编号的 $M$ 列火车在运行。
第 $i$ 列火车会在时刻 $S_i$ 从城市 $A_i$ 出发，并在时刻 $T_i$ 到达城市 $B_i$。

给定正整数 $X_1$，请你确定 $0$ 以上的整数 $X_2,\ldots,X_M$，使得它们满足以下条件，并且 $X_2+\ldots+X_M$ 最小。

• 条件：对于所有满足 $1\leq i,j\leq M$ 的组合 $(i,j)$，如果「$B_i=A_j$ 且 $T_i\leq S_j$」，那么「$T_i+X_i\leq S_j+X_j$」。
  • 也就是说，原本可以换乘的火车对，即使将每列火车 $i$ 的发车和到达时间都延迟 $X_i$，依然可以换乘。

可以证明，使 $X_2+\ldots+X_M$ 最小的 $X_2,\ldots,X_M$ 的取法是唯一的。

输入格式

输入按以下格式从标准输入读入。

$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

输入 #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

输入输出样例 #2

输入 #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

输入 #3

4 4 10
1 2 0 1
1 2 0 10
2 3 100 200
2 4 100 200

输出 #3

0 0 0

说明/提示

限制

• $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$
• 所有输入均为整数

样例说明 1

第 $1$ 列从城市 $1$ 到 $2$ 的火车到达时间延迟了 $15$，变为 $35$。
为了在城市 $2$ 换乘到第 $3$ 列火车，需要将第 $3$ 列火车的发车时间延迟 $10$，变为 $35$ 发车、$50$ 到达。
进一步，为了在城市 $3$ 换乘到第 $6$ 列火车，需要将第 $6$ 列火车的发车时间延迟 $5$，变为 $50$ 发车。
其他火车无需延迟发车，原本可以换乘的火车之间依然可以换乘，因此 $(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5)$ 满足条件。
而且不存在比这更小的和，因此这就是答案。

由 ChatGPT 4.1 翻译