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:
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:
#!/usr/bin/env python3
import sys
from collections import deque

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    dist = [[] for _ in range(N+1)]
    value = [None for _ in range(N+1)] ## value[i] i+1の値

    ## あるノードとつながっている「ノードと距離」を入れていく
    for i in range(M):
        dist[L[i]].append((R[i],D[i]))
        dist[R[i]].append((L[i],-D[i]))

    def BFS(queue):
        while queue:
            q = queue.popleft()
            q_value = value[q]

            for node_number, distance in dist[q]:
                if value[node_number] == None:
                    value[node_number] = q_value+distance
                    queue.append(node_number)
                else:
                    if value[node_number] == q_value+distance:
                        continue
                    else: ##矛盾してるからあうと
                        print(NO)
                        sys.exit()
    
    for index, v in enumerate(value):
        if index == 0:
            continue
        if v == None and dist[index]: 
            value[index] = 0
            BFS(deque([index]))

    print(YES)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    D = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, L, R, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

x = [None]*(N+1)
for i in range(1,N+1):
    if x[i] is not None: continue
    queue = [i]
    x[i] = 0
    minx = maxx = 0
    while len(queue)>0:
        queue_new = []
        for q in queue:
            for r, d in edges[q]:
                dist = x[q] + d
                if x[r]==None:
                    x[r] = dist
                    queue_new.append(r)
                elif x[r]!=dist:
                    print('No')
                    exit()
                    
        queue = queue_new

print('Yes')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v,w=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,w))
        E[v].append((u,-w))

    pos=[INF]*n # position
    def dfs(v)->NoneType:
        if(pos[v]!=INF): return
        pos[v]=0
        Q=[v]
        while(Q):
            v=Q.pop()
            for nv,w in E[v]:
                if(pos[nv]==INF):
                    pos[nv]=pos[v]+w
                    Q.append(nv)
                else:
                    if(pos[nv]!=pos[v]+w):
                        print("No")
                        exit(0)

    for v in range(n): dfs(v)
    print("Yes")
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v,w=map(int,input().split())
        u-=1; v-=1
        E[u].append((v,w))
        E[v].append((u,-w))

    pos=[INF]*n # position
    def dfs(v)->bool:
        if(pos[v]!=INF): return True
        pos[v]=0
        Q=[v]
        while(Q):
            v=Q.pop()
            for nv,w in E[v]:
                if(pos[nv]==INF):
                    pos[nv]=pos[v]+w
                    Q.append(nv)
                else:
                    if(pos[nv]!=pos[v]+w):
                        return False
        return True
    for v in range(n):
        if(not dfs(v)):
            print("No")
            return
    print("Yes")
resolve()

Submission status: Accepted

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

G = [{} for _ in range(N+1)]
for L, R, D in LRD:
    G[L][R] = D
    G[R][L] = -D

visited = [False] * (N+1)
dist = [0] * (N+1)


def dfs(v):
    q = [v]
    while q:
        cu = q.pop()
        for nx, d in G[cu].items():
            if visited[nx]:
                if dist[nx] != dist[cu] + d:
                    # print(nx, dist[nx], cu, dist[cu], d)
                    print('No')
                    exit()
            else:
                visited[nx] = True
                dist[nx] = dist[cu] + d
                q.append(nx)
    return True


for n in range(1, N+1):
    if not visited[n]:
        dfs(n)
print('Yes')

Submission status: Accepted

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

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

if M == 0:
    print('Yes')
    exit()

LRD = map(int, read().split())
graph = [[] for _ in range(N + 1)]

# 根からの距離、根は複数の可能性あり
distance = [-1] * (N + 1)
child = [0] * (N + 1)

for L, R, D in zip(LRD, LRD, LRD):
    graph[L].append((R, D))
    child[R] = 1

for i in range(1, N + 1):
    if child[i]:
        continue

    # 以下iは根
    distance[i] = 0
    stack = [i]
    while stack:
        V = stack.pop()
        for v, d in graph[V]:
            if distance[v] == -1:
                distance[v] = distance[V] + d
                stack.append(v)
            else:
                if distance[v] != distance[V] + d:
                    print('No')
                    exit()

# 例4のような循環タイプは上のfor内で処理されない
if -1 in set(distance[1:]):
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())



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=map(int,input().split())
	uf=WeightedUnionFind(n)
	
	for i in range(m):
		l,r,d=map(int,input().split())
		if uf.same(l,r):
			if d!=uf.diff(l,r):
				print("No")
				exit(0)
		else:
			uf.union(l,r,d)
	print("Yes")
	
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	q=deque()
	a=[None]*(n+1)

	for i in range(1,n+1):
		if a[i]==None:
			q=[i]
			a[i]=0
			while q:
				now=q.pop()
				for r,d in li[now]:
					if a[r]==None:
						a[r] = a[now] + d
						q.append(r)
					else:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    inf=10**10
    to = defaultdict(list)
    n, m = map(int, input().split())
    for _ in range(m):
        l, r, d = map(int, input().split())
        l, r = l - 1, r - 1
        to[l].append([r, d])
        to[r].append([l, -d])
    pos = [inf] * n
    for root in range(n):
        if pos[root] != inf: continue
        pos[root] = 0
        stack = [[root, 0]]
        while stack:
            u, p = stack.pop()
            for v, d in to[u]:
                if pos[v] == inf:
                    stack.append([v, p + d])
                    pos[v] = p + d
                else:
                    if pos[v] != p + d:
                        print("No")
                        exit()
    print("Yes")

main()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(n,fordfs):
    l = [None] * n
    g = fordfs
    for i in range(n):
        if l[i] != None:
            #チェック済みの点iはスキップ
            continue
        l[i] = 0
        que = deque()
        que.append(i)
        while que:
            d = que.pop()
            for node, cost in g[d]:
                if l[node] == None:
                    l[node] = l[d] + cost
                    que.append(node)
                else:
                    if l[node] != l[d] + cost:
                        print('No')
                        exit(0)
    print('Yes')
#    print(l)
    return
##############################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, M = LI()
g = [[] for _ in range(N)]
for i in range(M):
    x,y,z = map(int,input().split())
#    l = min(x,y)
#    r = max(x,y)
    g[x-1].append((y-1, z))
    g[y-1].append((x-1, -z))

bfs(N,g)

Submission status: Accepted

Solution code:
import sys

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.weight = [0]*n
    
    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):
        px = self.find(x)
        py = self.find(y)
        d = w - self.weight[x] + self.weight[y]
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
            self.weight[px] = d
        else:
            self.par[py] = px
            self.weight[py] = -d
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

for i in range(M):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    if G.same(l,r):
        if G.diff(l,r) != d:
            print("No")
            sys.exit()
    else:
        G.union(l,r,d)
    
print("Yes")

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
L = [0]*M
R = [0]*M
D = [0]*M
for i in range(M):
    L[i], R[i], D[i] = map(int, input().split())
    
G = [[] for _ in range(N)]
for i in range(M):
    G[L[i]-1].append([R[i]-1, D[i]])
    G[R[i]-1].append([L[i]-1, -D[i]])
    
ans = "Yes"
visited = ["?"]*N
for i in range(N):
    if visited[i] == "?":
        q = [[i, 0]]
        visited[i] = 0
        while len(q) > 0:
            temp = q.pop(-1)
            pos = temp[0]
            d = temp[1]
            for j in range(len(G[pos])):
                if visited[G[pos][j][0]] == "?":
                    q.append([G[pos][j][0], d+G[pos][j][1]])
                    visited[G[pos][j][0]] = d+G[pos][j][1]
                elif visited[G[pos][j][0]] != d+G[pos][j][1]:
                    ans = "No"
                    break

print(ans)

Submission status: Accepted

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

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

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

d = [None] * (N + 1)

def calc(start): #startからの連結成分をチェックする
    d[start] = 0
    stack = [start]
    while len(stack) != 0:
        tmp = stack.pop()
        for next_, diff in graph[tmp]:
            if d[next_] == None:
                d[next_] = d[tmp] + diff
                stack.append(next_)
            else:
                if d[next_] == d[tmp] + diff:
                    pass
                else:
                    print ('No')
                    exit()
    return 

# for i in graph:
#     print (i)

for i in range(1, N):
    if d[i] == None:
        calc(i)
print ('Yes')

Submission status: Accepted

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

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

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

d = ['a'] * (N + 1)

def calc(start): #startからの連結成分をチェックする
    d[start] = 0
    stack = [start]
    while len(stack) != 0:
        tmp = stack.pop()
        for next_, diff in graph[tmp]:
            if d[next_] == 'a':
                d[next_] = d[tmp] + diff
                stack.append(next_)
            else:
                if d[next_] == d[tmp] + diff:
                    pass
                else:
                    print ('No')
                    exit()
    return 

# for i in graph:
#     print (i)

for i in range(1, N):
    if d[i] == 'a':
        calc(i)
print ('Yes')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(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))
l = [None] * n
for i in range(n):
    if l[i] != None:
        continue
    l[i] = 0
    stack = [i]
    while stack:
        d = stack.pop()
        for node, cost in g[d]:
            if l[node] == None:
                l[node] = l[d] + cost
                stack.append(node)
            else:
                if l[node] != l[d] + cost:
                    print('No')
                    exit(0)
print('Yes')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
graph = [[] for i in range(n)]
x=[None for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    graph[b-1].append([a-1, -c])
    graph[a-1].append([b-1, c])
def fuck():
    for i in range(n):
        if x[i]==None:
            x[i]=0
            q=[i]
        while q:
            j=q.pop()
            for  d, e in graph[j]:
                if x[d]==None:
                    q.append(d)
                    x[d]=x[j]+e
                elif x[d]!=x[j]+e:
                    return False
    return True
if fuck():
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque
INFTY = 10**10
N,M = map(int,input().split())
ind = 2
if N==1:
    ind = 0
else:
    G = {}
    for _ in range(M):
        L,R,D = map(int,input().split())
        if L not in G:
            G[L]=[]
        G[L].append((R,D))
        if R not in G:
            G[R] = []
        G[R].append((L,-D))
    dist = [INFTY for _ in range(N+1)]
    hist = [0 for _ in range(N+1)]
    for i in G:
        ind = 2
        heap = deque([i])
        while heap:
            cur = heap.popleft()
            if hist[cur]==0:
                dist[cur] = 0
                hist[cur]=1
                ind = 0
            elif hist[cur]==1 and ind==2:
                break
            for x in G[cur]:
                v,w = x[0],x[1]
                if hist[v]==0:
                    dist[v] = dist[cur]+w
                    heap.append(v)
                    hist[v]=1
                else:
                    if dist[v]!=dist[cur]+w:
                        ind = 1
                        break
            if ind==1:break
        if ind==1:break
if ind!=1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[[]for _ in range(n+1)]
y=[None]*(n+1)
a="Yes"
for num in range(m):
	i,j,k=map(int,input().split())
	x[i].append((j,k))
	x[j].append((i,-k))
for i in range(1,n+1):
	if y[i]==None:
		y[i]=0;q=[i]
		while q:
			p=q.pop()
			for j,k in x[p]:
				if y[j]==None:q+=[j];y[j]=y[p]+k
for i in range(1,n+1):
	for j,k in x[i]:
		if y[i]+k!=y[j]:a="No"
print(a)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1,N+1)}
    dis = [0]*(N+1)
    for i in range(1,N+1):
        if not visited[i]:
            stk = [( i, -1, 0)]
            while stk:
                v, p, d = stk.pop()
                #print(v,p)
                if visited[v]:
                    if dis[v]!=dis[p]+d:
                        print("No")
                        exit()
                    continue
                visited[v] = True
                dis[v]=dis[p]+d
                for u,d in E[v]:
                    if u != p:
                        stk.append((u,v,d))
    print("Yes")
main()

Submission status: Accepted

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

ans = "Yes"
pos = [INF]*N
for i in range(N):
  if pos[i]==INF:
    que = [[i,0]]
    while(que):
      c,cp = que.pop()
      if pos[c]==INF:
        pos[c] = cp
        for n,d in node[c]:
          if pos[n]==INF:
            que.append([n,cp+d])
          elif pos[n] != cp+d:
            ans="No"
            break
        else:
          continue
        break
      elif pos[c] != cp:
        ans="No"
        break
    else:
      continue
    break
print(ans)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
es = [collections.deque() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    es[l].append((l, r, d))
    es[r].append((r, l, -d))

visited = [False] * n
for i in range(n):
    if not visited[i]:
        visited[i] = True
        if len(es[i]) == 0:
            continue
        distances = [float('inf')] * n
        distances[i] = 0
        q = collections.deque()
        for e in es[i]:
            q.append(e)
        while q:
            j, k, d = q.popleft()
            if visited[k] and distances[k] != distances[j] + d:
                print('No')
                exit()
            distances[k] = distances[j] + d
            visited[k] = True
            while es[k]:
                ee = es[k].popleft()
                if len(es[ee[1]]) > 0:
                    q.append(ee)
print('Yes')

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(S):
        i_order = []
        temp_order = []
        level = 0
        while S:
            v1 = S.pop()
            if used[v1[0]]:
                continue
            if v1[1]<level:
                for _ in range(len(temp_order)-v1[1]):
                    x = temp_order.pop()
                    i_order.append(x)
                level = v1[1]
            level += 1
            if not used[v1[0]]:
                for v1_to in G[v1[0]]:
                    if not used[v1_to]:
                        S.append((v1_to,level))
                temp_order.append(v1[0])
                used[v1[0]] = True
        for t in reversed(temp_order):
            i_order.append(t)
        return i_order
    for i in range(N):
        if not used[i]:
            i_order = dfs([(i,0)])
            order += i_order
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = II()
if M>0:
    L,R,D = Line(M,3)
else:
    print('Yes')
    exit()

pt = edges_to_pt(L,R,N)
label,group = scc(N,pt,pt)

x = []
used = [False]*label
for i in range(N):
    if not used[group[i]]:
        x.append(i)
        used[group[i]] = True

pt_l = [[] for _ in range(N)]
for i in range(M):
    pt_l[L[i]-1].append((R[i]-1,D[i]))
    pt_l[R[i]-1].append((L[i]-1,-D[i]))

check_visited = [False]*N
l = [None]*N 
for v in x:
    check_visited[v] = True
    l[v] = 0
    S = [v]
    while S:
        v1 = S.pop()
        for i in pt_l[v1]:
            if check_visited[i[0]] == False:
                check_visited[i[0]] = True
                l[i[0]] = l[v1] + i[1]
                S.append(i[0])
            else:
                if l[i[0]] == l[v1] + i[1]:
                    continue
                else:
                    print('No')
                    exit()

print('Yes')

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N, M = map(int, input().split())
e = dd(list)
inf = 10 ** 9
pos = [inf] * (N + 1)
for i in range(M):
  a, b, d = map(int, input().split())
  e[a].append((b, d))
  e[b].append((a, -d))
visited = [0] * (N + 1)
s = []
for i in range(1, N + 1):
  if visited[i] == 0:
    s.append(i)
    pos[i] = 0
  while len(s):
    p = s.pop()
    for q in e[p]:
      if pos[q[0]] == inf:
        pos[q[0]] = pos[p] + q[1]
        visited[q[0]] = 1
        s.append(q[0])
      else:
        if pos[q[0]] - pos[p] != q[1]:
          print("No")
          exit(0)
print("Yes")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
D = [list(map(int, input().split())) for i in range(m)]

A = [0] * (n+1)

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

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

V = [0] * (n+1)


# print(M)

for ii in range(1, n+1):
    if V[ii] == 0 and len(M[ii]) > 0:

        Q = [[ii, 0]]
        st = 0
        while st < len(Q):
            # print(A,V,Q)
            node = Q[st][0]
            dist = Q[st][1]
            if V[node] == 0 and len(M[node]) > 0:
                V[node] = 1
                A[node] += dist
                for i in M[node]:
                    if V[i[0]] == 0:
                        Q.append([i[0], A[node] + i[1]])
            st += 1

# print(A)

def d():
    for i in range(m):
        if A[D[i][1]] - A[D[i][0]] != D[i][2]:
            return "No"
    return "Yes"

print(d())

Submission status: Accepted

Solution code:
def sol():
    n,m=map(int,input().split())
    t,w={},{}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w: w[l].add((r,d))
        else: w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    chk=set()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        chk.add((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=t[(i,x[0])]+j[1]:
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        #t[(i,j[0])]=t[(i,x[0])]+j[1]
                        t[(i,j[0])]=x[1]+j[1]
                        chk.add((j[0],x[1]+j[1]))
    print("Yes")

if __name__=="__main__":
    sol()

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)
        self.flag = 0
 
    # 検索
    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)
        
        if rx == ry:
            if self.diff(x,y) != w:
                self.flag = 1
        # 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():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    flag = 0
    A = WeightedUnionFind(N)
    for i in range(M):
        L,R,D = map(int,input().split())
        A.union(L,R,D)
            
    if A.flag == 1:
        print("No")
    else:
        print("Yes")
    
    
main()