3365. [USACO20 Feb Gold]Timeline

【题目描述】

Bessie 在过去的 $M$ 天（$2 \le M \le 10^9$）内参加了 $N$ 次（$1\le N\le 10^5$）挤奶。然而，她不太记得她是什么时候参加每次挤奶了。

对于每次挤奶 $i = 1 \ldots N$，她知道这次挤奶的时间不早于第 $S_i$ 天（$1\le S_i\le M$）。此外，Bessie 记得 $C$ 件事，每一件可以用一个三元组 $(a,b,x)$ 表示，表示她记得第 $b$ 次挤奶在第 $a$ 次挤奶之后至少 $x$ 天。

请帮助 Bessie 计算每次挤奶最早可能的日期。保证 Bessie 没有记错；换而言之，存在一种在范围 $1\ldots M$ 内的挤奶时间的安排能够满足她的所有记忆。

【输入格式】

输入的第一行包含 $N$、$M$ 和 $C$。

下一行包含 $N$ 个空格分隔的整数 $S_1,S_2,\ldots, S_N$。每个数均在范围 $1 \ldots M$ 之内。

以下 $C$ 行每行包含三个整数 $a$、$b$ 和 $x$，表示第 $b$ 次挤奶在第 $a$ 次挤奶之后至少 $x$ 天。对于每一行，$a \neq b$，$a$ 和 $b$ 在范围 $1 \ldots N$ 内，且 $x$ 在范围 $1 \ldots M$ 内。

【输出格式】

输出 $N$ 行，为每次挤奶最早可能的日期。

【样例输入】

4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4

【样例输出】

1
6
3
8

【样例解释】

第二次挤奶发生在第一次挤奶之后至少五天，所以它不可能发生在第 $1+5=6$ 天前。第四次挤奶发生在第二次挤奶之后至少两天，所以它不可能发生在第 $6+2=8$ 天前。

【提示】

对于$ 40\% $的测试数据(测试点$ 1 \sim 4 $)，满足$ N , C ≤ 10^3 $。  

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 二月公开赛 Gold 组