该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Hidden Weights

题目描述

给你一个有向图，包含 $N$ 个顶点和 $M$ 条有向边。第 $j$ 条有向边从顶点 $u_j$ 指向顶点 $v_j$，权值为 $w_j$。 找出一种方法，对每个顶点写下一个位于 $-10^{18}$ 到 $10^{18}$（含端点）之间的整数，使下述条件成立。

设 $x_i$ 为写在顶点 $i$ 上的值。对于所有边 $j=1,2,\dots,M$，皆有 $x_{v_j} - x_{u_j} = w_j$。

保证对给定输入至少存在一种这样的赋值。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $u_1$ $v_1$ $w_1$ $u_2$ $v_2$ $w_2$ $\vdots$ $u_M$ $v_M$ $w_M$

输出格式

设 $x_i$ 为写在顶点 $i$ 上的整数。按顺序输出 $x_1, x_2, \dots, x_N$，用空格分隔，全部在一行上。如果有多种解，可以输出其中任意一种。

3 3
1 2 2
3 2 3
1 3 -1

3 5 2

4 2
2 1 5
3 4 -3

5 0 6 3

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

200401298 182231955 -106709603 69445364 278499365

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq M \leq \min\{2 \times 10^5,N(N-1)/2\}$ $1 \leq u_j, v_j \leq N$ $u_j \neq v_j$ 若 $i \neq j$，则 $(u_i, v_i) \neq (u_j, v_j)$ 且 $(u_i, v_i) \neq (v_j, u_j)$ $|w_j| \leq 10^9$ 所有输入值均为整数。 存在至少一种满足条件的赋值。通过设 $x = (3, 5, 2)$，我们有 $x_2 - x_1 = w_1 = 2$、$x_2 - x_3 = w_2 = 3$、$x_3 - x_1 = w_3 = -1$，满足条件。 例如，$x = (-1, 1, -2)$ 也是一个有效答案。
例如，$x = (0, -5, 4, 1)$ 和 $x = (5, 0, 4, 1)$ 也是有效答案。

标签: AtCoder|abc373D

来源

AtCoder|abc373D