Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())

Tree = [[] for _ in range(N)]
for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    Tree[L].append((R,D))
    Tree[R].append((L,-D))

num = dict()
for i in range(N):
    if i not in num:
        num[i] = 0
        Q = deque(Tree[i])
        x = 0
        while Q:
            now,d = Q.popleft()
            if now in num:
                if num[now] != d:
                    print("No")
                    exit()
            else:
                num[now] = d
                for node,Di in Tree[now]:
                    Q.append((node,d+Di))
print("Yes")

Submission status: Accepted

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        # 親ノードとの重み
        self.diff_weight = [0 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        # 親ノードはまだ上書きしない
        root = self.find(self.par[x])
        self.diff_weight[x] += self.diff_weight[self.par[x]]
        self.par[x] = root
        return self.par[x]

    def weight(self, x):
        # xの根に対する重みを返す
        self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        #xの根と yの根の差分をとる
        return self.weight(y) - self.weight(x)

    def unite(self, x, y, w):
        # ノード x の下にノード y をつける。辺の重みは w
        # x の根と y の 根をくっつけるのでwを補正する
        w += self.weight(x)
        w -= self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            # y の下に x をつけることになるので、重さは反転させる
            self.par[x] = y
            w = -w
            self.diff_weight[x] = w
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
            self.diff_weight[y] = w
        else:
            self.par[y] = x
            self.rank[x] += 1
            self.diff_weight[y] = w

n, m = map(int, input().split())
wuf = WeightedUnionFind(n)
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if wuf.find(l) == wuf.find(r):
        if wuf.diff(l, r) != d:
            print('No')
            exit()
    else:
        wuf.unite(l, r, d)
else:
    print('Yes')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
T = [[] for _ in range(N+1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    T[L].append((R, D))
    T[R].append((L, -D))
X = [None] * (N + 1)
for i in range(1, N+1):
    if X[i] is not None: continue
    X[i] = 0
    stack = [i]
    while stack:
        L = stack.pop()
        for R, D in T[L]:
            if X[R] is None:
                X[R] = X[L] + D
                stack.append(R)
            else:
                if X[R] - X[L] != D:
                    print("No")
                    exit()
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque

class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N, M = map(int, input().split())

edges = [[] for _ in range(N + 1)]
tree = UnionFind(N + 1)
for _ in range(M):
    left, right, dist = map(int, input().split())
    edges[left].append((right, dist))
    edges[right].append((left, -dist))
    tree.union(left, right)

minDist = [None] * (N + 1)
for start in range(1, N + 1):
    if tree.root(start) != start:
        continue

    que = deque([(start, 0)])
    while que:
        now, dist = que.popleft()

        if minDist[now] == None:
            minDist[now] = dist
        else:
            if minDist[now] != dist:
                print('No')
                exit()
            continue

        for to, d in edges[now]:
            que.append((to, dist + d))

print('Yes')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[y] - self.weight[x]


N,M=map(int,input().split())
uf=WeightedUnionFind(N)

for i in range(M):
    #print(a)
    #print(uf.weight)
    L,R,D=map(int,input().split())
    L-=1
    R-=1

    if uf.same(L,R):
        if uf.diff(L,R)!=D:
            print("No")
            exit()
    else:
        uf.union(L,R,-D)
        #a[R]=a[L]+D
#print(a)
print("Yes")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())

#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*n
wei = [0]*n
"""
重さが追加されるのは、yの方。
yにxの重さとwの合計が記録される。
"""
for i in range(m):
    l,r,d = map(int,input().split())
    l,r = l-1,r-1
    if same(l,r):#矛盾が生じる条件は、lとrが同じグループにいて、その重さの差の辻褄が合わなかったとき
        if d != diff(l,r):
            print("No")
            exit()
    else:
        unite(l,r,d)
print("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    ### 重み付き
    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
# unionfindで同じクラスタに属すか判定
# 同じクラスタ内では拘束条件を適用する
# 重み付きunionfindを使おう
uf = UnionFind(N)
for i in range(M):
    l, r, d = map(int, input().split())
    if not uf.judge(l,r):
        uf.weighted_union(l,r,d)
    else:
        if uf.weight[r]-uf.weight[l]!=d:
            print("No")
            exit()

print("Yes")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())

edge = [list(map(int,input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for e in edge:
    graph[e[0]-1].append((e[1]-1,e[2]))
    graph[e[1]-1].append((e[0]-1,-e[2]))

level = [None for _ in range(N)]

inconsistent = False

for i in range(N):
    if level[i] is None:
        level[i] = 0
        stack = [i]
        while stack:
            node = stack.pop()
            for adj,cost in graph[node]:
                if level[adj] is None:
                    level[adj] = level[node] + cost
                    stack.append(adj)
                else:
                    if level[adj] != level[node] + cost:
                        inconsistent = True
                        break
    if inconsistent:
        break

if inconsistent:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
#https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_1_B/review/3161450/jakenu0x5e/Python3

import sys
readline = sys.stdin.readline
write = sys.stdout.write

n,m = map(int, readline().split())
*p, = range(n+1)
data = [0]*(n+1)

def root(x):
    if x == p[x]:
        return x
    r = p[x]
    p[x] = y = root(r)
    data[x] += data[r]

    return y
    
def unite(x, y, z):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        data[py] = data[x] - data[y] + z
    else:
        p[px] = py
        data[px] = data[y] - data[x] - z
    return 1


ans = []

for i in range(m):
    li,ri,di = map(int, readline().split())
    pl = root(li); pr = root(ri)
    if pl == pr:
        if data[ri] - data[li] != di:
            print("No")
            exit()
    else:
        unite(li,ri,di)
#print(data)        
print("Yes")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
q = [list(map(int, input().split())) for i in range(m)]

g = [[] for i in range(n+1)]

for i in range(m):
    a, b, c = q[i]
    g[a].append((b, c))
    g[b].append((a, -c))

people = [-10**10] * (n+1)

flag = 1
for i in range(1, n+1):
    if people[i] != -10**10:
        continue
    q = [i]
    people[i] = 0
    while q:
        now = q.pop()
        for next, dist in g[now]:
            if people[next] == -10**10:
                q.append(next)
                people[next] = people[now] + dist
            else:
                if people[next] == people[now] + dist:
                    continue
                else:
                    flag = 0
                    break
        if flag == 0:
            break

if max(people[1:]) - min(people[1:]) > 10**9:
    flag = 0

if flag == 1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    def find(x):
        if par[x] < 0:
            return x
        else:
            px = find(par[x])
            wei[x] += wei[par[x]]
            par[x] = px
            return px

    def weight(x):
        find(x)
        return wei[x]


    def unite(x,y,w):
        w += wei[x]-wei[y]
        x = find(x)
        y = find(y)
        
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
                w = -w
            par[x] += par[y]
            par[y] = x
            wei[y] = w
            return True

    def same(x,y):
        return find(x) == find(y)

    def size(x):
        return -par[find(x)]

    def diff(x,y):
        return weight(y)-weight(x)

    n,m = map(int,input().split())


    par = [-1]*n
    wei = [0]*n

    for i in range(m):
        l,r,d = map(int,input().split())
        l,r = l-1,r-1
        if same(l,r):
            if d != diff(l,r):
                print('No')
                exit()
        else:
            unite(l,r,d)
    print('Yes')
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class WUnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []
    DIFF_WEIGHT=[]

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * n
        self.DIFF_WEIGHT=[ 0 ] * n

    def root(self,x):
        if self.PAR[x] == x:
            return x
        else:
            r = self.root(self.PAR[x])
            self.DIFF_WEIGHT[x] += self.DIFF_WEIGHT[self.PAR[x]]
            self.PAR[x] = r
            return r
    
    def weight(self,x):
        self.root(x)
        return self.DIFF_WEIGHT[x]

    def issame(self,x,y):
        return self.root(x) == self.root(y)

    def diff(self,x,y):
        return self.weight(y)-self.weight(x)

    def merge(self,x,y,w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.RANK[x] < self.RANK[y]:
            x,y = y,x
            w = -w
        if self.RANK[x] == self.RANK[y]:
            self.RANK[x] += 1

        self.PAR[y] = x
        self.DIFF_WEIGHT[y] = w
        return True


N,M  = map(int,input().split())
Ans = []
tree = WUnionFind(N+1)
b = True
for _ in range(M):
    l,r,d = map(int,input().split())
    if tree.issame(l,r) and tree.diff(l,r) != d:
        b = False
        break
    tree.merge(l,r,d)

if b:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())

root = list(range(n+1))
height = [0] * (n + 1)

def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def merge(v, u):
    rv = find_root(v)
    ru = find_root(u)
    if rv != ru:
        if height[v] >= height[u]:
            root[ru] = rv
            height[v] = max(height[v], height[v] + 1)
        else:
            root[rv] = ru

graph = [[] for _ in range(n+1)]
for l, r, d in zip(*[map(int, sys.stdin.read().split())] * 3):
    graph[l].append((r, d))
    graph[r].append((l, -d))
    merge(l, r)

for v in range(1, n+1):
        find_root(v)

def main():
    dist = [None] * (n + 1)
    for v in set(root[1:]):
        dist[v] = 0
        stack = [v]
        while stack:
            x = stack.pop()
            for y, d in graph[x]:
                if dist[y] is None:
                    dist[y] = dist[x] + d
                    stack.append(y)
                elif dist[y] != dist[x] + d:
                    return 'No'
    return 'Yes'
      
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for l, r, d in zip(*[map(int, sys.stdin.read().split())] * 3):
    graph[l].append((r, d))
    graph[r].append((l, -d))

root = list(range(n+1))
height = [0] * (n + 1)

def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def merge(v, u):
    rv = find_root(v)
    ru = find_root(u)
    if rv != ru:
        if height[v] >= height[u]:
            root[ru] = rv
            height[v] = max(height[v], height[v] + 1)
        else:
            root[rv] = ru

def main():
    for v in range(1, n+1):
        for u, d in graph[v]:
            merge(v, u)

    for v in range(1, n+1):
        find_root(v)
        
    dist = [None] * (n + 1)
    for v in set(root[1:]):
        dist[v] = 0
        stack = [v]
        while stack:
            x = stack.pop()
            for y, d in graph[x]:
                if dist[y] is None:
                    dist[y] = dist[x] + d
                    stack.append(y)
                elif dist[y] != dist[x] + d:
                    return 'No'
    return 'Yes'
      
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[13]:


import sys
from collections import deque
input = sys.stdin.readline


# In[14]:


N, M = map(int, input().split())


# In[2]:


link = [[] for _ in range(N)]
for _ in range(M):
    L, R, D = map(int, input().split())
    link[L-1].append((R-1, D))
    link[R-1].append((L-1, -D))


# In[9]:


def func():
    houmon = [False] * N
    x = [0] * N
    
    for start in range(N):
        if houmon[start]:
            continue
        stack = deque([start])
        while stack:
            n1 = stack.pop()
            houmon[n1] = True
            for n2, d in link[n1]:
                if houmon[n2]:
                    if x[n2] != x[n1] + d:
                        return False
                else:
                    x[n2] = x[n1] + d
                    stack.append(n2)
        
#         if max(x) - min(x) > 10 ** 9:
#             return False
    
    return True


# In[10]:


if func():
    print('Yes')
else:
    print('No')


# In[ ]:

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for l, r, d in zip(*[map(int, sys.stdin.read().split())] * 3):
    graph[l].append((r, d))
    graph[r].append((l, -d))

def main():
    dist = [None] * (n + 1)
    i = 1
    while i <= n:
        if dist[i] is not None:
            i += 1
            continue
        dist[i] = 0
        stack = [i]
        while stack:
            x = stack.pop()
            for y, d in graph[x]:
                if dist[y] is None:
                    dist[y] = dist[x] + d
                    stack.append(y)
                elif dist[y] != dist[x] + d:
                    return 'No'
    return 'Yes'

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 10
dist = [INF] * (N + 1)

graph = [[] for _ in range(N + 1)]
for i in range(M):
  L, R, D = LRD[i]
  graph[L].append((R, D))
  graph[R].append((L, -D))
#print("graph:", graph)

for i in range(1, N + 1):
  if dist[i] == INF:
    stack = [i]
    dist[i] = 0
    max_d = 0
    min_d = 0
    
    while stack:
      l = stack.pop()
      for r, d in graph[l]:
        if dist[r] != INF:
          if dist[r] != dist[l] + d:
            print("No")
            exit()
          else:
            continue
        else:
          stack.append(r)
          dist[r] = dist[l] + d
#print("dist:", dist)
print("Yes")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class WeightedUnionFind:
    """ 重み付きUnion-Find木 """

    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    def find(self, x):
        """ 検索 """
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w):
        """ 併合 """
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = - w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        """ 同じ集合に属するか """
        return self.find(x) == self.find(y)

    def diff(self, x, y):
        """ xからyへのコスト """
        return self.weight[x] - self.weight[y]

N, M = MAP()
wuf = WeightedUnionFind(N)
for i in range(M):
    l, r, d = MAP()
    # 既に同じ集合にあるなら、距離が正しいか確認
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            No()
            exit()
    else:
        wuf.union(l, r, d)
Yes()

Submission status: Accepted

Solution code:
n, m, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
vis = [None] * n
for l, r, d in zip(*[iter(L)] * 3):
	con[l - 1] += [(r - 1, d)]
	con[r - 1] += [(l - 1, -d)]

def check(s):
	if vis[s] is not None:
		return True
	q = [s]
	vis[s] = 0
	while q:
		cur = q.pop()
		for nxt, d in con[cur]:
			if vis[nxt] is not None:
				if vis[nxt] != vis[cur] + d:
					return False
				continue
			vis[nxt] = vis[cur] + d
			q += [nxt]
	return True

print("Yes" if all(check(s) for s in range(n)) else "No")

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline


n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
edges = defaultdict(list)

for i in range(m):
    left, right, dist = map(int, input().split())
    edges[left-1].append((right-1, dist))
    edges[right-1].append((left-1, -dist))

seen = [None] * n
for node in range(n):
    if seen[node] is not None:
        continue

    seen[node] = 0
    todo = []
    while edges[node]:
        to, dis = edges[node].pop()
        seen[to] = dis
        todo.append([to, dis])

    while todo:
        new, dis = todo.pop()

        while edges[new]:
            to, n_dis = edges[new].pop()
            if seen[to] is None:
                seen[to] = dis + n_dis
            elif seen[to] != dis + n_dis:
                print('No')
                exit()
            todo.append([to, dis + n_dis])

print('Yes')

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
inf = float('INF')

n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
edges = defaultdict(list)

for i in range(m):
    left, right, dist = map(int, input().split())
    edges[left-1].append([right-1, dist])
    edges[right-1].append([left-1, -dist])

seen = [inf] * n
for node in range(n):
    if seen[node] != inf:
        continue

    seen[node] = 0
    todo = []
    while edges[node]:
        to, dis = edges[node].pop()
        todo.append([to, dis])
    while todo:
        new, dis = todo.pop()
        if seen[new] == inf:
            seen[new] = dis
        elif seen[new] != dis:
            print('No')
            exit()

        while edges[new]:
            to, n_dis = edges[new].pop()
            todo.append([to, dis + n_dis])

print('Yes')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[None]*n
g=[[] for _ in range(n)]
for _ in range(m):
    l,r,d=map(int,input().split())
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
for i in range(n):
    if a[i]==None:
        a[i]=0
        q=[i]
    while q:
        j=q.pop()
        for x,e in g[j]:
            if a[x]==None:
                a[x]=a[j]+e
                q.append(x)
            elif a[x]!=a[j]+e:
                print("No")
                exit()
                
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, input().split())
    X[l-1].append((r-1, d))
    X[r-1].append((l-1, -d))

done = [0] * N
dist = [0] * N
def BFS(i):
    Q = deque([i])
    done[i] = 1
    while Q:
        x = Q.popleft()
        for y, d in X[x]:
            if done[y]:
                if dist[y] != dist[x] + d:
                    return 0
            else:
                done[y] = 1
                dist[y] = dist[x] + d
                Q.append(y)
    return 1

for i in range(N):
    if done[i] == 0:
        if BFS(i) == 0:
            print("No")
            break
else:
    print("Yes")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = [i for i in range(N)]
D = [0] * N
C = [1] * N

def par(a):
    if a == P[a]:
        return a
    p = par(P[a])
    d = D[P[a]]
    P[a] = p
    D[a] += d
    return p

def dist(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb:
        return D[b] - D[a]
    return 1 << 30

def unite(a, b, d):
    if par(a) == par(b):
        return
    if C[P[a]] < C[P[b]]:
        a, b, d = b, a, -d
    C[P[a]] += C[P[b]]
    D[P[b]] = D[a] + d - D[b]
    P[P[b]] = P[a]

for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    dd = dist(l, r)
    if dd == 1<<30:
        unite(l, r, d)
    else:
        if d != dd:
            print("No")
            break
else:
    print("Yes")

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()
c=[]
x=[inf]*n
ans=True
g=[[] for _ in range(n)]
for i in range(m):
    l,r,d=LI_()
    d+=1
    g[l].append((r,d))
    g[r].append((l,-d))
    c.append((l,r,d))

v=[inf]*n
vs=[-1]*n

def bfs(st):
    if v[st]!=inf:
        return True
    q=[st]
    v[st]=0
    vs[st]=0
    while q:
        
        c=q.pop()
        for nb,d in g[c]:
            if vs[nb]==0:
                continue
            else:
                q.append(nb)
                vs[nb]=0
                if v[nb]==inf:
                    v[nb]=v[c]+d
                elif v[nb]!=v[c]+d:
                    show(c+1,nb+1,v)
                    return False
    return True

for i in range(n):
    if bfs(i):
        continue
    else:
        print('No')
        exit()

for i in range(m):
    l,r,d=c[i]
    if v[l]+d!=v[r]:
        print('No')
        exit()
        
print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

graph = {j:[] for j in range(n)}
for i in range(m):
    l, r, d = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    graph[l].append((r, d))
    graph[r].append((l, -d))

already = set()
x_ls = [None for i in range(n)]
x_ls[0] = 0
stack = list(range(n))[::-1]
flg = True
while len(stack) > 0:
    cur = stack.pop(-1)
    if cur in already:
        continue
    if x_ls[cur] is None:
        cur_pos = 0
    else:
        cur_pos = x_ls[cur]
    already.add(cur)
    for _next, dis in graph[cur]:
        if x_ls[_next] is None:
            x_ls[_next] = cur_pos + dis
            stack.append(_next)
        else:
            if x_ls[_next] != cur_pos + dis:
                flg = False
                break
    if not flg:
        break
if flg:
    print("Yes")
else:
    print("No")