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())
G=[[] for i in range(n)]
dist=[None]*n
for i 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):
    q=deque()
    if dist[i]==None:
        dist[i]=0
        q.append(i)
    while q:
        cur=q.popleft()
        for nx,d in G[cur]:
            if dist[nx]==None:
                dist[nx]=dist[cur]+d
                q.append(nx)
            elif dist[nx]!=dist[cur]+d:
                print('No')
                exit()
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, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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)
			else:  # 閉路⇒条件チェック
				if num[node]-num[n] != weight:
					print("No")
					exit()

print("Yes")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

visited = [False] * N
dist = [float('inf')] * N
for i in range(N):
    if not visited[i]:
        dist[i] = 0
        stack = [i]
        while stack:
            v = stack.pop()
            visited[v] = True
            for u, d in G[v]:
                if dist[u] == float('inf'):
                    dist[u] = dist[v] + d
                elif dist[u] != dist[v] + d:
                    print('No')
                    exit()
                if not visited[u]:
                    stack.append(u)
print('Yes')

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
connection=[[] for i in range(n)]
for i in range(m):
  connection[l[i][0]-1].append((l[i][1]-1,l[i][2]))
  connection[l[i][1]-1].append((l[i][0]-1,-l[i][2]))

distance=[-999999999999]*n
visited=[-1]*n

def bfs(v):
  distance[v]=0
  next=[v]
  next2=set()
  visitct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j][0]]==-1:
            distance[connection[next[i]][j][0]]=distance[next[i]]+connection[next[i]][j][1]
            next2.add(connection[next[i]][j][0])
    next=list(next2)
    next2=set()

for i in range(n):
  if distance[i]==-999999999999:
    bfs(i)

for i in range(m):
  if distance[l[i][1]-1]-distance[l[i][0]-1]!=l[i][2]:
    print('No')
    sys.exit()
print('Yes')

Submission status: Accepted

Solution code:
N, M, *LRD = map(int, open(0).read().split())

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

visited = [False] * (N + 1)
D = [0] * (N + 1)
for i in range(1, N + 1):
    if visited[i]:
        continue

    S = [i]
    while S:
        v = S.pop()
        for u, d in E[v]:
            if not visited[u]:
                visited[u] = True
                D[u] = D[v] + d
                S.append(u)

            elif D[u] != D[v] + d:
                print("No")
                quit()

print("Yes")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,-tmp[2]])
from collections import deque
INF=10**10
dist=[INF]*n
for i in range(n):
    if dist[i]!=INF:
        continue
    dist[i]=0
    Q = deque()
    Q.append([i,0])
    while Q:
        now,cnt = Q.popleft()
        for nxt,nxt_dist in link[now]:
            if dist[nxt] == INF:
                dist[nxt] = cnt+nxt_dist
                Q.append([nxt,cnt+nxt_dist])
            elif dist[nxt] != cnt+nxt_dist:
                    print("No")
                    exit()

print("Yes")

Submission status: Accepted

Solution code:
import collections
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    flag=True
    while len(d):
        x = d.popleft()
        for i,j in vec[x]:
            if dis[i] == INF:
                dis[i]=dis[x]+j
                d.append(i)
 
            else:
                if dis[i]==dis[x]+j:
                    continue
                else:
                    print('No')
                    exit()
    return flag
 
 
n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]
 
for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))
 
INF=float('inf')
dis=[INF]*n
 
for i in range(n):
    if dis[i]==INF:
        bfs(i)
print('Yes')

Submission status: Accepted

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

def bfs(s):
    d = deque()
    d.append(s)
    dis[s]=0
    flag=True
    while len(d):
        x = d.popleft()
        for i,j in vec[x]:
            if dis[i] == INF:
                dis[i]=dis[x]+j
                d.append(i)

            else:
                if dis[i]==dis[x]+j:
                    continue
                else:
                    print('No')
                    exit()
    return flag


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]

for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))

INF=float('inf')
dis=[INF]*n

for i in range(n):
    if dis[i]==INF:
        bfs(i)
print('Yes')

Submission status: Accepted

Solution code:
import collections
from collections import deque

def Dfs(now):
    flag = True
    d = deque()
    d.append(now)
    visited[now]=0
    while len(d):
        now = d.pop()
        for i,j in vec[now]:
            if visited[i]==INF:
                d.append(i)
                visited[i]=visited[now]+j
            else:
                if visited[i]==visited[now]+j:
                    continue
                else:
                    flag=False
                    break
    return flag


n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
vec= [[] for i in range(n)]

for i in range(m):
    vec[a[i][0]-1].append((a[i][1]-1,a[i][2]))
    vec[a[i][1]-1].append((a[i][0]-1,-a[i][2]))

INF=float('inf')
visited=[INF]*n

for i in range(n):
    if visited[i]==INF:
        if not Dfs(i):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  l, r, d = map(int, input().split())
  l -= 1
  r -= 1
  G[l].append((r, d))
  G[r].append((l, -d))
dist = [float("inf")]*n
def dfs(v):
  for nv, d in G[v]:
    if dist[nv] == float("inf"):
      dist[nv] = dist[v]+d
      if not dfs(nv):
        return False
    else:
      if dist[nv] != dist[v]+d:
        return False
  return True
for i in range(n):
  if dist[i] == float("inf"):
    dist[i] = 0
    if not dfs(i):
      print("No")
      break
else:
  print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
LRD = []
P = [float('inf') for i in range(N)]
Edges = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    Edges[R].append((L,-D))
    Edges[L].append((R,D))
for i in range(N):
    Q = deque()
    if P[i] == float('inf'):
        P[i] = 0
        Q.append(i)
    while Q:
        current_pos = Q.popleft()
        for next_pos, d in Edges[current_pos]:
            if P[next_pos] == float('inf'):
                P[next_pos] = P[current_pos] + d
                Q.append(next_pos)
            else:
                if P[next_pos] != P[current_pos] + d:
                    print('No')
                    exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


N,M=map(int,input().split())
adj=[[] for _ in range(N)]
inf = 10**9+1
x=[inf]*N

L=[0]*M
R=[0]*M
D=[0]*M
fro=[0]*N#何個入ってくる？

for i in range(M):
    L[i],R[i],D[i]=map(int,input().split())
    L[i]-=1
    R[i]-=1
    adj[L[i]].append([R[i],D[i]])
    fro[R[i]]+=1
    #adj[R[i]].append([L[i],-1*D[i]])
    
    
roots=[]
for i in range(N):
    if fro[i]==0:
        roots.append(i)

queue=[]
#距離の設定
for root in roots:
    if x[root]==inf:
        queue.append([root,-1])#node,pare
        x[root]=0
        while queue:
            node,par=queue.pop()
            num=len(adj[node])
            for i in range(num):
                to,cost=adj[node][i]
                if x[to]==inf:#見たことがなければ
                    x[to]=x[node]+cost
                    queue.append([to,node])
            
    
f=1
#判定
for i in range(M):
    d=x[R[i]]-x[L[i]]
    if d!=D[i]:
        f=0
            
    
    
            
            
            
if f==1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# D - People on a Line
from collections import deque
n,m=map(int,input().split())
dist=[None]*n
edge=[[] for i in range(n)]

for i in range(m):
    l,r,d=map(int,input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))

for i in range(n):
    q=deque()
    if dist[i]==None:
        dist[i]=0
        q.append(i)
    while q:
        cur=q.popleft()
        for nx,d in edge[cur]:
            if dist[nx]==None:
                dist[nx]=dist[cur]+d
                q.append(nx)
            elif dist[nx]!=dist[cur]+d:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

Solution code:
from collections import defaultdict


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

edges = defaultdict(list)

for i in range(m):
    l, r, d = map(int, input().split())
    edges[l-1].append([r-1, d])
    edges[r-1].append([l-1, -d])

seen = [float('INF')] * n

for start in range(n):
    if seen[start] != float('INF'):
        continue

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

    while todo:
        node, dist = todo.pop()

        while edges[node]:
            to, add_dis = edges[node].pop()

            if seen[to] == float('INF') or seen[to] == dist+add_dis:
                seen[to] = dist + add_dis
                todo.append([to, dist+add_dis])

            else:
                print('No')
                exit()

print('Yes')

Submission status: Accepted

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


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.weight = [0]*N

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            p = self.root(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = p
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y, w):
        w -= self.getWeight(x)
        w += self.getWeight(y)
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.weight[x] = self.weight[y]+w
            return

    def getWeight(self, x):
        x -= 1
        self.root(x)
        return(self.weight[x])


G = unionFind(N)
flag = True

for l, r, d in LRD:
    if G.same(l, r) == False:
        G.unite(l, r, d)
    else:
        if G.getWeight(l) - G.getWeight(r) == d:
            continue
        else:
            flag = False
            break

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

Submission status: Accepted

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

from collections import deque
human = ["0"]*N
ans = "Yes"
for i in range(N):
    if ans == "No":
        break
    if len(E[i]) == 0:
        continue
    if human[i] == "0":
        human[i] = 0
        q = deque([i])
        while q:
            temp = q.popleft()
            for e in E[temp]:
                if human[e[0]] == "0":
                    human[e[0]] = human[temp]+e[1]
                    q.append(e[0])
                elif human[e[0]] != human[temp]+e[1]:
                    ans = "No"
                    break
    else:
        for e in E[i]:
            if human[e[0]] != human[i]+e[1]:
                ans = "No"
                break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
used = [True]*N
dic = defaultdict(list)
for i in range(M):
  l, r, d = map(int,input().split())
  l -= 1
  r -= 1
  used[r] = False
  dic[l] += [(r,d)]

dist = [-1]*N
q = deque([])
for i in range(N):
  if used[i]:
    q += [i]
    dist[i] = 0

ans = True
while q:
  e = q.popleft()
  flag = False
  for p, d in dic[e]:
    if dist[p]==-1:
      dist[p] = d+dist[e]
      q += [p]
    elif dist[p]!=dist[e]+d:
      ans = False
      flag = True
      break
  if flag:
    break
if ans:
  if -1 not in dist:
    print('Yes')
  else:
    print('No')
else:
  print('No')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
N, M = [int(_) for _ in input().split()]

LRD = []
path = [[] for _ in range(N + 1)]
for _ in range(M):
    l, r, d = [int(_) for _ in input().split()]
    path[l].append((r, d))
    path[r].append((l, -d))
    LRD.append((l, r, d))

INF = -1e12
memo = [INF] * (N + 1)


def dfs(n):
    for ni, d in path[n]:
        if memo[ni] != INF: continue
        memo[ni] = memo[n] + d
        dfs(ni)


for i in range(1, N + 1):
    if memo[i] != INF: continue
    memo[i] = 0
    dfs(i)
for l, r, d in LRD:
    if memo[l] + d != memo[r] and memo[l] - d != memo[r]:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

e_IN = [[] for _ in range(N+1)]
e_OUT = [[] for _ in range(N+1)]

for _ in range(M):
    l, r, d = map(int, readline().split())
    e_OUT[l].append((r, d))
    e_IN[r].append((l, d))

posx = [-1] * (N + 1)


def dfs(v):
    #　0<=x<=10**9に注意
    node = [v]
    posx[v] = 0
    diameter = 0
    while node:
        s = node.pop()
        ds = posx[s]
        for t, dt in e_OUT[s]:
            dist = ds + dt
            if posx[t] != -1:
                if posx[t] != dist:
                    return False
                else:
                    continue
            posx[t] = dist
            node.append(t)
            diameter = max(diameter, dist)
    if diameter <= 10 ** 9:
        return True
    else:
        return False


ans = "Yes"
for i in range(N + 1):
    if len(e_IN[i]) == 0:
        posx[i] = 0
        bl = dfs(i)
        if not bl:
            ans = "No"
            break

if - 1 in posx:
    ans = "No"

print(ans)

Submission status: Accepted

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

e_IN = [[] for _ in range(N+1)]
e_OUT = [[] for _ in range(N+1)]

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

posx = [-1] * (N + 1)


def dfs(v):
    #　0<=x<=10**9に注意
    node = [v]
    posx[v] = 0
    diameter = 0
    while node:
        s = node.pop()
        ds = posx[s]
        for t, dt in e_OUT[s]:
            dist = ds + dt
            if posx[t] != -1:
                if posx[t] != dist:
                    return False
                else:
                    continue
            posx[t] = dist
            node.append(t)
            diameter = max(diameter, dist)
    if diameter <= 10 ** 9:
        return True
    else:
        return False


ans = "Yes"
for i in range(N + 1):
    if len(e_IN[i]) == 0:
        posx[i] = 0
        bl = dfs(i)
        if not bl:
            ans = "No"
            break

if - 1 in posx:
    ans = "No"

print(ans)

Submission status: Accepted

Solution code:
class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.weight = [0]*N

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            p = self.root(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = p
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y, w):
        w-=self.getWeight(x)
        w+=self.getWeight(y)
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.weight[x] = self.weight[y]+w
            return
    def getWeight(self,x):
      x-=1
      self.root(x)
      return(self.weight[x])
N,M=map(int,input().split())
G=unionFind(N)
LRD=[tuple(map(int,input().split())) for i in range(M)]
for l,r,d in LRD:
  #print(G.parent)
  #print(G.weight)
  if G.same(l,r):
    if G.getWeight(r)-G.getWeight(l) == d:
      continue
    else:
      #print(G.parent)
      #print(G.weight)
      print("No")
      exit(0)
  else:
    G.unite(r,l,d)

print("Yes")

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)
def fix(x):
    q = []
    while root[x]!=x:
        q.append(x)
        x = root[x]
    rt = x
    while  len(q)>0:
        x = q.pop()
        dist[x] += dist[root[x]]
        root[x] = rt
    return rt

n,m = inm()
root = list(range(n))
dist = [0]*n
for i in range(m):
    l,r,d = inm()
    l -= 1
    r -= 1
    rtl = fix(l)
    rtr = fix(r)
    if rtl != rtr:
        #ddprint(f'rtl {rtl} rtr {rtr} dl {dist[l]} dr {dist[r]}')
        if dist[l]+d > dist[r]:
            dist[rtr] = dist[l]+d-dist[r]
            dist[r] = dist[l]+d
            root[r] = root[rtr] = rtl
        else:
            dist[rtl] = dist[r]-dist[l]-d
            #dist[l] += dist[rtl]
            dist[l] = dist[r]-d
            root[l] = root[rtl] = rtr
    else:
        if dist[l]+d != dist[r]:
            print('No')
            exit()
    #ddprint(f'l {l} r {r} d {d}')
    #ddprint(root)
    #ddprint(dist)
print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
data = []
inf = 10**10
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    l,r,d = map(int, input().split())
    adjacent_list[l].append([r,d])
    adjacent_list[r].append([l,-d])
finished = set()
x = [0 for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for nex, dis in adjacent_list[node]:
        if nex not in finished:
            x[nex] = x[node] + dis
            dfs(nex)
        else:
            if x[nex] != x[node] + dis:
                print("No")
                exit()
for i in range(1,n+1):
    if i not in finished:
        dfs(i)
print("Yes")

Submission status: Accepted

Solution code:
# D - People on a Line

import sys
sys.setrecursionlimit(10000000)

N, M = map(int, sys.stdin.buffer.readline().split())
LRD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

LRD = [[LRD[i][0]-1, LRD[i][1]-1, LRD[i][2]] for i in range(M)]

if N == 1 or M == 0:
    print("Yes")
    exit()

neighbor = [[] for _ in range(N)]
for i in range(M):
    neighbor[LRD[i][0]].append([LRD[i][1], LRD[i][2]])
    neighbor[LRD[i][1]].append([LRD[i][0], -LRD[i][2]])

x = [None] * N

def check(i):
    if x[i] == None:
        x[i] = 0
    for next_point, dist in neighbor[i]:
        if x[next_point] == None:
            x[next_point] = x[i] + dist
            check(next_point)
        elif x[next_point] != x[i] + dist:
            print('No')
            exit()

for i in range(N):
    if x[i] == None:
        check(i)

print('Yes')

Submission status: Accepted

Solution code:
#http://at274.hatenablog.com/entry/2018/02/03/140504
#重み付きUnion-Find木

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]

import sys
input = sys.stdin.readline  #文字列入力では注意！

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

for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L,R) != D:
            print("No")
            break
    else:
        uf.union(L,R,D)
else:
    print("Yes")

Submission status: Accepted

Solution code:
#http://at274.hatenablog.com/entry/2018/02/03/140504
#重み付きUnion-Find木

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)

for _ in range(M):
    L,R,D = map(int,input().split())
    L -= 1; R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L,R) != D:
            print("No")
            break
    else:
        uf.union(L,R,D)
else:
    print("Yes")

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 複数回出てきているところが問題、グラフ問題として連結した部分で判定
N, M = lr()
adjacent = [[] for _ in range(N+1)] # 1-indexed
for _ in range(M):
    l, r, d = lr()
    adjacent[l].append((r, d))
    adjacent[r].append((l, -d))

X = [None] * (N+1)

def check(i):
    if X[i] == None: X[i] = 0
    for target, dist in adjacent[i]:
        if X[target] == None:
            X[target] = X[i] + dist
            check(target)
        elif X[target] != X[i] + dist:
            print('No')
            exit()

for i in range(1, N+1):
    if X[i] == None:
        check(i)

print('Yes')
# 54

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 複数回出てきているところが問題、グラフ問題として連結した部分で判定
N, M = lr()
adjacent = [[] for _ in range(N+1)] # 1-indexed
for _ in range(M):
    l, r, d = lr()
    adjacent[l].append((r, d))
    adjacent[r].append((l, -d))

X = [None] * (N+1)
used = set()

def check(i):
    global used
    used.add(i)
    if X[i] == None: X[i] = 0
    for target, dist in adjacent[i]:
        if X[target] != None and X[target] != X[i] + dist:
            print('No')
            exit()
        if target in used:
            continue
        else:
            X[target] = X[i] + dist
            check(target)

for i in range(1, N+1):
    check(i)

print('Yes')
# 54

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    dist = [[] for _ in range(N)]
    
    for i in range(M):
        l,r,d = map(int,input().split())
        dist[l-1].append((r-1,d))
        dist[r-1].append((l-1,-d))
        
    go = [None for _ in range(N)]
    for i in range(N):
        if go[i] is None:
            go[i] = 0
        q = deque([i])
        while q:
            l = q.pop()
            for r,d in dist[l]:
                if go[r] is None:
                    go[r] = go[l] + d
                    q.append(r)
                else:
                    if go[r] - go[l] != d:
                        print("No")
                        exit()
        
    print("Yes")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class WeightedUnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.weight = [0 for _ in range(n)]
    def find(self,x):
        root = x
        stack = [root]
        while self.parents[root] != root:
            root = self.parents[root]
            stack.append(root)
        while stack:
            s = stack.pop()
            self.weight[s] += self.weight[self.parents[s]]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y,w):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.weight[xroot] = w-self.weight[x]+self.weight[y]
        else:
            self.parents[yroot] = xroot
            self.weight[yroot] = -w+self.weight[x]-self.weight[y]
            if xrank == yrank:
                self.rank[xroot] += 1
    def diff(self,x,y):
        return self.weight[x]-self.weight[y]

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

for _ in range(M):
    l,r,d = map(int,input().split())
    if uf.find(l-1) == uf.find(r-1):
        if uf.diff(l-1,r-1) != d:
            print('No')
            break
    else:
        uf.unite(l-1,r-1,d)
else:
    print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline  #文字列入力では注意！

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

num = dict()
for i in range(N):
    if i not in num:
        num[i] = 0
        Q = deque(Graph[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 Graph[now]:
                    Q.append((node,d+Di))
print("Yes")