Abc373 D - Hidden Weights

给定一个有 N 个顶点和 M 条边的有向图。第 j 条有向边从顶点 u j 到顶点 v j，权重为 w j 。

找到一种方法将一个介于 −10 18 和 10 18

之间的整数（含）写入每个顶点，以满足以下条件。

让 xi 成为顶点

i 上写入的值。对于所有边

j=1,2,…,M，它成立

x

v j  −x uj =w j 。

保证给定输入至少存在一个这样的分配。

约束

2≤N≤2×10 5

如果 i!=j，则 (u i ,v i !=(u j ,v j ) 且 (u i ,v i )

=(v j ,u j )∣wj ∣≤10 9

所有输入值均为整数。

至少存在一个满足条件的赋值。

输入

输入来自标准输入，格式如下：

N

M

u 1 v 1 w 1

u 2 v 2 w 2

⋮

u M v M w M

输出

设 x i 为顶点 i 上写的整数。按此顺序在一行上打印 x 1 ,x 2 ,…,x N

，以空格分隔。如果有多个解决方案，您可以打印其中任何一个。

示例输入 1

3 3

1 2 2

3 2 3

1 3 -1

示例输出 1

3 5 2

通过设置 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) 也是一个有效答案。

示例输入 2

4 2

2 1 5

3 4 -3

示例输出 2

5 0 6 3

例如，

x=(0,−5,4,1) 和 x=(5,0,4,1) 也是有效答案。

--------

说一下当时没做出来的地方，1：建图的时候，要建双向的图，不然就可能会没遍历完，同时这里建双向图的时候，一个是正数，一个数负数，素以就是用数组来存储，然后就是要做2个循环，当时就做了一个循环，因为可能有的位置没有遍历到，然后去bfs即可，结果我用的dfs。。做题少了，没有想好建图的方法，没有想好遍历的方法。结果WA了。