Train Delay

题目描述

在 Atcoder 国，有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 列火车，编号为 $1$ 到 $M$。 第 $i$ 列火车于时间 $S_i$ 从城市 $A_i$ 出发，并于时间 $T_i$ 到达城市 $B_i$。 给定正整数 $X_1$，请找到一种方法设置非负整数 $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$。

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

0 10 0 0 5

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

100 100 100 100 100 100 100 100

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

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$ 到 $2$ 的到达时间被延迟了 $15$，变为时间 $35$。
为了允许在城市 $2$ 从列车 $1$ 换乘到列车 $3$，列车 $3$ 的出发时间被延迟了 $10$，使其在时间 $35$ 出发并在时间 $50$ 到达。
此外，为了允许在城市 $3$ 从列车 $3$ 换乘到列车 $6$，列车 $6$ 的出发时间被延迟了 $5$，使其在时间 $50$ 出发。
其他列车可以在不延迟的情况下运行，同时仍然允许原本可换乘的列车之间的换乘，因此 $(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5)$ 满足该条件。
此外，不存在和更小的满足条件的解，因此这是答案。

标签: AtCoder|abc368E

来源

AtCoder|abc368E