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:
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
    
def main():
    class Unionfind():
        def __init__(self,n):
            self.parents=[-1]*n
            self.dist=[0]*n 
        
        def find(self,x):
            if self.parents[x]<0:
                return self.dist[x],x
            else:
                tmp=self.find(self.parents[x])
                self.dist[x]+=tmp[0]
                self.parents[x]=tmp[1]
            return self.dist[x], self.parents[x]
        
        def union(self,x,y,d):
            rx=self.find(x)[1]
            ry=self.find(y)[1]
            diff=self.dist[y]-self.dist[x]-d
            if rx==ry:
                if diff!=0:
                    return True
                return False
            if diff<0:
                rx,ry=ry,rx
                diff=-diff
            self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
            self.parents[rx]=ry
            self.dist[rx]=diff
            return False
    n,m,*lrd=map(int,read().split())
    edg=[]
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()

Submission status: Accepted

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x,self.dist[x]
        else:
            tmp=self.find(self.parents[x])
            self.parents[x]=tmp[0]
            self.dist[x]+=tmp[1]
            return self.parents[x],self.dist[x]
    
    def union(self,x,y,d):
        rx,_=self.find(x)
        ry,_=self.find(y)
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Accepted

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

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        l, r, d = ns()
        l, r = l - 1, r - 1
        e[l].append([r, d])
        e[r].append([l, -d])

    visited = [False] * n
    dist_mat = [INF] * n

    for i in range(n):
        if visited[i]:
            continue
        que = collections.deque()
        que.append([i, 0])
        visited[i] = True
        dist_mat[i] = 0
        while que:
            idx, dist = que.popleft()
            for ei, di in e[idx]:
                if visited[ei]:
                    if dist + di == dist_mat[ei]:
                        continue
                    else:
                        print("No")
                        exit(0)
                else:
                    visited[ei] = True
                    dist_mat[ei] = dist + di
                    que.append([ei, dist + di])

    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n , m = map(int,input().split())
z = [[] for i in range(n)]
for i in range(m):
    l , r , d = map(int,input().split())
    z[l-1].append((r-1,d))
    z[r-1].append((l-1,-d))

visit = [False for i in range(n)]
x = [-1 for i in range(n)]
for i in range(n):
    if visit[i]:
        continue
    visit[i] = True
    q = deque()
    q.append(i)
    x[i] = 0
    while q:
        now = q.popleft()
        for t , d in z[now]:
            if not visit[t]:
                visit[t] = True
                x[t] = x[now] + d
                q.append(t)
            elif visit[t]:
                if x[t] - x[now] != d:
                    print("No")
                    exit()
print("Yes")

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for i in range(m):
        l,r,d = map(int,ipt().split())
        way[l].append((r,d))
        way[r].append((l,-d))
    q = []

    pl = [10**18]*(n+1)
    for i in range(1,n+1):
        if pl[i] != 10**18:
            continue
        q.append(i)
        pl[i] = 0
        while q:
            qi = q.pop()
            pq = pl[qi]
            for j,dj in way[qi]:
                if pl[j] == 10**18:
                    pl[j] = pq+dj
                    q.append(j)
                elif pl[j] != pq+dj:
                    print("No")
                    exit()
    print("Yes")

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**17


def main():

    N, M = in_nn()
    LRD = in_nl2(M)

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

    for i in range(M):
        l, r, d = LRD[i]
        l, r = l - 1, r - 1
        edge[l].append((r, d))
        edge[r].append((l, -d))

    v_set = []
    search = [False] * N

    def bfs(N, v0, edge):

        search[v0] = True
        q = deque()
        q.append(v0)

        while q:
            v = q.popleft()
            for nv, _ in edge[v]:
                if not search[nv]:
                    q.append(nv)
                    search[nv] = True

    for i in range(N):
        if not search[i]:
            bfs(N, i, edge)
            v_set.append(i)

    def judge(v0):

        search = defaultdict(lambda: False)
        search[v0] = True

        q = deque()
        q.append(v0)

        pos = defaultdict(lambda: INF)
        pos[v0] = 0

        vs = [v0]

        while q:
            v = q.popleft()
            now_pos = pos[v]
            for nv, dis in edge[v]:
                if pos[nv] == INF:
                    pos[nv] = now_pos + dis
                elif pos[nv] - now_pos != dis:
                    return False
                if not search[nv]:
                    q.append(nv)
                    search[nv] = True
                    vs.append(nv)

        max_pos = -INF
        min_pos = INF
        for tv in vs:
            tp = pos[tv]
            max_pos = max(max_pos, tp)
            min_pos = min(min_pos, tp)

        return max_pos - min_pos <= 10**9 + 1

    ans = 'Yes'
    for v in v_set:
        if not judge(v):
            ans = 'No'

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M = MAP()
 
graph = defaultdict(list)
for _ in range(M):
	L, R, D = MAP()
	graph[L-1].append((R-1, D))
	graph[R-1].append((L-1, -D))
 
num = [None]*N

for i in range(N):
	if num[i] != None:
		continue
	q = deque([i])
	num[i] = 0
	while q:
		n = q.popleft()
		for node, weight in graph[n]:
			if num[node] == None:
				num[node] = num[n] + weight
				q.append(node)
			elif num[node] != num[n] + weight:
				print("No")
				exit()

else:
	print("Yes")

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFindWeighted:
    # Reference:
    # https://note.nkmk.me/python-union-find/
    # https://at274.hatenablog.com/entry/2018/02/03/140504
    # https://qiita.com/drken/items/cce6fc5c579051e64fab
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = root
            return root

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.parents[rx] > self.parents[ry]:
            x, y, rx, ry, w = y, x, ry, rx, -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = self.weight[x] - self.weight[y] + w

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

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


def main():
    N, M, *LRD = map(int, read().split())

    uf = UnionFindWeighted(N)
    for l, r, d in zip(*[iter(LRD)] * 3):
        l -= 1
        r -= 1
        if uf.same(l, r) and uf.diff(l, r) != d:
            print('No')
            return
        else:
            uf.union(l, r, d)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFindWeighted:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = root
            return root

    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.parents[rx] > self.parents[ry]:
            x, y, rx, ry, w = y, x, ry, rx, -w

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.weight[ry] = self.weight[x] - self.weight[y] - w

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

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


def main():
    N, M, *LRD = map(int, read().split())

    uf = UnionFindWeighted(N)
    for l, r, d in zip(*[iter(LRD)] * 3):
        l -= 1
        r -= 1
        if uf.same(l, r) and uf.diff(l, r) != d:
            print('No')
            return
        else:
            uf.union(l, r, d)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
dic = {i:[] for i in range(1,N+1)}

for _ in range(M):
  l, r, d = map(int, input().split())
  dic[l].append((r,d))
  dic[r].append((l,-d))

memo = [0]*(N+1)
h = deque([])

for i in range(1,N+1):
  if memo[i] > 0:
    continue
  h.append((i,0))
  while h:
    t = h.popleft()
    for u in dic[t[0]]:
      if u[0] == t[1]:
        continue
      if memo[u[0]] == 0:
        memo[u[0]] = memo[t[0]] + u[1]
        h.append((u[0],t[0]))
      else:
        if memo[u[0]] - memo[t[0]] != u[1]:
          print('No')
          exit()
          
print('Yes')

Submission status: Accepted

Solution code:
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[x] - self.weight[y]

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

wuf = WeightedUnionFind(N)

for _ in range(M):
  l, r, d = map(int, input().split())
  if wuf.same(l,r):
    if wuf.diff(l,r) != d:
      print('No')
      exit()
  else:
    wuf.union(l,r,d)
    
print('Yes')

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M = MAP()
LRD = [LIST() for _ in range(M)]

graph = [[] for _ in range(N)]
for L, R, D in LRD:
	graph[L-1].append((R-1, D))
	graph[R-1].append((L-1, -D))

check = [1]*N
i = 0
while 1:
	while check[i] == 0:
		i += 1
		if i == N:
			print("Yes")
			exit()

	check[i] = 0
	dis = defaultdict(int)
	dis[i] = 0
	q = deque([i])
	while q:
		p = q.popleft()
		for v, dist in graph[p]:
			if check[v] == 1:
				check[v] = 0
				dis[v] = dis[p] + dist
				q.append(v)
			if check[v] == 0 and dis[v] != dis[p] + dist:
				print("No")
				exit()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M = MAP()
LRD = [LIST() for _ in range(M)]

graph = [[] for _ in range(N)]
for L, R, D in LRD:
	graph[L-1].append((R-1, D))
	graph[R-1].append((L-1, -D))

check = [1]*N
i = 0
while i < N:
	while check[i] == 0:
		i += 1
		if i == N:
			print("Yes")
			exit()

	check[i] = 0
	dis = defaultdict(int)
	dis[i] = 0
	q = deque([i])
	while q:
		p = q.popleft()
		for v, dist in graph[p]:
			if check[v] == 1:
				check[v] = 0
				dis[v] = dis[p] + dist
				q.append(v)
			if check[v] == 0 and dis[v] != dis[p] + dist:
				print("No")
				exit()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M = MAP()
LRD = [LIST() for _ in range(M)]

graph = [[] for _ in range(N)]
for L, R, D in LRD:
	graph[L-1].append((R-1, D))
	graph[R-1].append((L-1, -D))

check = [1]*N
i = 0
while i < N:
	while check[i] == 0:
		i += 1
		if i == N:
			print("Yes")
			exit()

	check[i] = 0
	dis = defaultdict(int)
	dis[i] = 0
	q = deque([i])
	while q:
		p = q.popleft()
		for v, dist in graph[p]:
			if check[v] == 1:
				check[v] = 0
				dis[v] = dis[p] + dist
				q.append(v)
			if check[v] == 0 and dis[v] != dis[p] + dist:
				print("No")
				exit()

Submission status: Accepted

Solution code:
# https://at274.hatenablog.com/entry/2018/02/03/140504
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[x] - self.weight[y]

N,M=map(int,input().split())
uf = WeightedUnionFind(N+1)
for i in range(M):
  l,r,d=map(int,input().split())
  if l>r:
    l,r=r,l
    d=-d
  if uf.same(l,r) and d != uf.diff(l,r):
    print('No')
    exit()
  uf.union(l,r,d)
print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFindWeighted:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = root
            return root

    def union(self, x, y, w):
        w += -self.weight[x] + self.weight[y]

        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y, w = y, x, -w

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.weight[y] = -w

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

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


def main():
    N, M, *LRD = map(int, read().split())

    uf = UnionFindWeighted(N)
    for l, r, d in zip(*[iter(LRD)] * 3):
        l -= 1
        r -= 1
        if uf.same(l, r) and uf.diff(l, r) != d:
            print('No')
            return
        else:
            uf.union(l, r, d)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


# https://at274.hatenablog.com/entry/2018/02/03/140504
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[x] - self.weight[y]


def main():
    N, M, *LRD = map(int, read().split())

    uf = WeightedUnionFind(N)
    for l, r, d in zip(*[iter(LRD)] * 3):
        l -= 1
        r -= 1
        if uf.same(l, r) and uf.diff(l, r) != d:
            print('No')
            return
        else:
            uf.union(l, r, d)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *LRD = map(int, read().split())

    G = [[] for _ in range(N)]
    for l, r, d in zip(*[iter(LRD)] * 3):
        G[l - 1].append((r - 1, d))
        G[r - 1].append((l - 1, -d))

    seen = [False] * N
    dist = [-1] * N
    for i in range(N):
        if seen[i]:
            continue

        dist[i] = 0
        queue = deque([i])
        while queue:
            v = queue.popleft()
            for nv, d in G[v]:
                if seen[nv]:
                    if dist[nv] != dist[v] + d:
                        print('No')
                        return
                else:
                    dist[nv] = dist[v] + d
                    seen[nv] = True
                    queue.append(nv)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *LRD = map(int, read().split())

    G = [[] for _ in range(N)]
    for l, r, d in zip(*[iter(LRD)] * 3):
        G[l - 1].append((r - 1, d))
        G[r - 1].append((l - 1, -d))

    dist = [INF] * N
    for i in range(N):
        if dist[i] != INF:
            continue

        dist[i] = 0
        queue = deque([i])
        while queue:
            v = queue.popleft()
            for nv, d in G[v]:
                if dist[nv] != INF:
                    if dist[nv] != dist[v] + d:
                        print('No')
                        return
                else:
                    dist[nv] = dist[v] + d
                    queue.append(nv)

    print('Yes')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    visit = [0] * (n + 1)
    e = [0] * (m + 1)
    x = [0] * (n + 1)
    q = deque()
    for i in range(1, n + 1):
        if not visit[i]:
            q.append(i)
            visit[i] = 1
            while q:
                j = q.popleft()
                for g in G[j]:
                    if not e[g[2]]:
                        #print(e, visit, q, x, j)
                        e[g[2]] = 1
                        if not visit[g[0]]:
                            x[g[0]] = g[1] + x[j]
                            visit[g[0]] = 1
                            q.append(g[0])
                        else:
                            #print(x[g[0]], g[1] + x[j])
                            if not x[g[0]] == g[1] + x[j]:
                                return False
    return True

n, m = map(int, input().split())
G = [[] for _ in range(n + 1)]
for i in range(m):
    l, r, d = map(int, input().split())
    G[l].append([r, d, i])
    G[r].append([l, -d, i])
print("Yes" if bfs() else "No")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
INF=10**18
e=[[]for _ in range(n+1)]
for _ in range(m):
  l,r,d=map(int,input().split())
  e[l]+=[(r,d)]
  e[r]+=[(l,-d)]
d=[INF]*(n+1)
for i in range(n+1):
  if d[i]!=INF:continue
  d[i]=0
  q=[i]
  while q:
    now=q.pop()
    for to,dist in e[now]:
      if d[to]==INF:
        d[to]=d[now]+dist
        q+=[to]
      else:
        if d[to]!=d[now]+dist:
          print('No')
          exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    edges[l-1].append((r-1, d))
    edges[r-1].append((l-1, -d))

visited = {}
# その人へのパスが複数あり、距離が異なる場合は矛盾
for i in range(N):
    if i in visited:
        continue

    # 連結グラフごとに相対的な距離を決定
    # dist = [0 for _ in range(N)]
    q = deque([(i, 0)])
    while q:
        l, c = q.popleft()
        if l in visited:
            if visited[l] != c:
                print("No")
                sys.exit()
            continue
        
        visited[l] = c
        # dist[l] = c

        for r, nd in edges[l]:
            q.append((r, c+nd))
    # print(dist)

print("Yes")