103684: [Atcoder]ABC368 E - Train Delay
Description
Score : $475$ points
Problem Statement
In the nation of Atcoder, there are $N$ cities numbered $1$ to $N$, and $M$ trains numbered $1$ to $M$. Train $i$ departs from city $A_i$ at time $S_i$ and arrives at city $B_i$ at time $T_i$.
Given a positive integer $X_1$, find a way to set non-negative integers $X_2,\ldots,X_M$ that satisfies the following condition with the minimum possible value of $X_2+\ldots+X_M$.
- Condition: For all pairs $(i,j)$ satisfying $1 \leq i,j \leq M$, if $B_i=A_j$ and $T_i \leq S_j$, then $T_i+X_i \leq S_j+X_j$.
- In other words, for any pair of trains that are originally possible to transfer between, it is still possible to transfer even after delaying the departure and arrival times of each train $i$ by $X_i$.
It can be proved that such a way to set $X_2,\ldots,X_M$ with the minimum possible value of $X_2+\ldots+X_M$ is unique.
Constraints
- $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$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $X_1$ $A_1$ $B_1$ $S_1$ $T_1$ $\vdots$ $A_M$ $B_M$ $S_M$ $T_M$
Output
Print $X_2,\ldots,X_M$ that satisfy the condition with the minimum possible sum, in that order, separated by spaces.
Sample Input 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
Sample Output 1
0 10 0 0 5
The arrival of train $1$ from city $1$ to $2$ is delayed by $15$ and becomes time $35$.
To allow transfer from train $1$ to $3$ in city $2$, the departure of train $3$ is delayed by $10$, making it depart at time $35$ and arrive at time $50$.
Further, to allow transfer from train $3$ to $6$ in city $3$, the departure of train $6$ is delayed by $5$, making it depart at time $50$.
Other trains can operate without delay while still allowing transfers between originally transferable trains, so $(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5)$ satisfies the condition.
Moreover, there is no solution with a smaller sum that satisfies the condition, so this is the answer.
Sample Input 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
Sample Output 2
100 100 100 100 100 100 100 100
Sample Input 3
4 4 10 1 2 0 1 1 2 0 10 2 3 100 200 2 4 100 200
Sample Output 3
0 0 0
Output
得分：475分
问题陈述
在Atcoder国，有N个城市，编号为1到N，和M列火车，编号为1到M。 火车i从城市A_i在时间S_i出发，到达城市B_i在时间T_i。
给定一个正整数X_1，找到一种方式设置非负整数X_2,…,X_M，使得以下条件满足，且X_2+…+X_M的值尽可能小。
- 条件：对于所有满足1≤i,j≤M的数对(i,j)，如果B_i=A_j且T_i≤S_j，那么T_i+X_i≤S_j+X_j。
- 换句话说，对于任何原本可能换乘的两列火车，即使在每列火车i的出发和到达时间延迟X_i后，仍然可以换乘。
可以证明，以最小可能的X_2+…+X_M值设置X_2,…,X_M的方式是唯一的。
约束条件
- 2≤N≤2×10^5
- 2≤M≤2×10^5
- 1≤A_i,B_i≤N
- A_i≠B_i
- 0≤S_i
- 1≤X_1≤10^9
- 所有输入值都是整数。
输入
输入从标准输入以以下格式给出：
N M X_1 A_1 B_1 S_1 T_1 … A_M B_M S_M T_M
输出
按顺序打印满足条件且和最小的X_2,…,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到城市2的火车1到达时间延迟了15，变为时间35。
为了允许在火车1和火车3在城市2之间换乘，火车3的出发时间延迟了10，使其在时间35出发并在时间50到达。
此外，为了允许在火车3和火车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