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: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
x = [None] * (N+1)

def dfs(s):
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            if not dfs(t):
                return False
        else:
            if x[t] != x[s] + d:
                return False
    return True

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])

ans = True
for i in range(N):
    if x[i] is None:
        x[i] = 0
        ans &= dfs(i)

print("Yes" if ans else "No")

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
x = [None] * (N+1)

def fail():
    print("No")
    # exit()

def dfs(s):
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            dfs(t)
        else:
            if x[t] != x[s] + d:
                fail()

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 x[i] is None:
        x[i] = 0
        dfs(i)

print("Yes")

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
x = [None] * (N+1)

def fail():
    print("No")
    exit()

def dfs(s):
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            dfs(t)
        else:
            if x[t] != x[s] + d:
                fail()

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 x[i] is None:
        x[i] = 0
        dfs(i)

print("Yes")

Submission status: Runtime Error

Solution code:
def dfs(s):
	global x, G
	for t, d in G[s]:
		if x[t] is None:
			x[t] = x[s] + d
			if not dfs(t):
				return False
		else:
			if x[t] != x[s] + d:
				return False
	return True

N,M = map(int,input().split())
x = [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])
print(G)
res = True
for i in range(N):
	if x[i] is None:
		x[i] = 0
		res &= dfs(i)

print("Yes" if res == True else "No")

Submission status: Runtime Error

Solution code:
n,m = (int(i) for i in input().split())

A = [0]*2*100000

for i in range(m):
    xr,xl,d = [int(i) for i in input().split()]
    if xr in A and xl in A:
        if A.index(xr) + d != A.index(xl):
            print("No")
            break
    elif xr in A:
        A[A.index(xr)+d] = xl
    elif xl in A:
        A[A.index(xl)-d] = xr
    else:
        A[xr+n-1] = xr
        A[xr+n-1+d] = xl
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
x = [None] * (N+1)

def fail():
    print("No")
    exit()

def dfs(s):
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            dfs(t)
        else:
            if x[t] != x[s] + d:
                fail()

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

for i in range(N):
    if x[i] is None:
        x[i] = 0
        dfs(i)

print("Yes")

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for i in range(M) ]
x = [-1]*(N+1)
unsolve = LRD

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

def sr(unsolves):
    nextUnsolve = []
    for u in unsolves:
        l, r, d = u
        if x[l] == -1 and x[r] == -1:
            nextUnsolve.append(u)
        elif x[l] == -1:
            x[l] = x[r] - d
        elif x[r] == -1:
            x[r] = x[l] + d
        else:
            if x[r] != x[l] + d:
                print("No")
                exit()
    if not not nextUnsolve:
        sr(nextUnsolve)

x[LRD[0][0]] = 0
sr(unsolve)

print("Yes")

Submission status: Runtime Error

Solution code:
from collections import deque

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

X = [0 for _ in range(N+1)]
edges = [[] for _ in range(M+1)]

contradiction = False

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

searched = set()
q = deque()

# assign x coordinate for each vertex
for i in range(N+1):
    if i in searched:
        continue
    q.append(i)
    searched.add(i)
    X[i] = 0
    while len(q) != 0:
        a = q.pop()
        for b, d in edges[a]:
            if b not in searched:
                q.append(b)
                searched.add(b)
                X[b] = X[a] + d
            else:
                if X[b] != X[a] + d:
                    contradiction = True
                    print("No")
                    break
        if contradiction:
            break
    if contradiction:
        break    
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
from collections import deque

#幅優先探索でラベリング
def bfs(x, graph, people):
    #people[x] is None -> まだ訪問していない．訪問していたらなラベルがつくので，
    if people[x] is not None:
        return
    unvisited = deque([x])
    people[x] = 0
    while unvisited:
        now = unvisited.popleft()
        for Next, d in graph:
            if people[Next] is None:
                people[Next] = people[now] + d
                unvisited.append(Next)

def main():
    N, M = list(map(int, input().split()))
    graph = [ [] for i in range(N)]
    people = [None] * N

    #グラフの作成
    for i in range(M):
        L, R, D = list(map(int, input().split()))
        graph[L].append((R, D))
        graph[R].append((L, -D))
    #全ての頂点でサーチ ->ラベリングを行う
    for i in range(N):
        bfs(i, graph, people)

    for i in range(N):
        for j,d in graph[i]:
            if people[j] - people[i] != d:
                print("No")
                exit()
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
M = int(input())
D = [[int(i) for i in input().split()] for i in range(M)]

eq = [[0 for i in range(N+1)] for j in range(M)]
eq2 = [[0 for i in range(N)] for j in range(M)]
for i in range(M):
    eq[i][D[i][0]-1] = 1
    eq[i][D[i][1]-1] = -1
    eq[i][N] = D[i][2]
    eq2[i][D[i][0]-1] = 1
    eq2[i][D[i][1]-1] = -1
    
if(np.linalg.matrix_rank(eq) == np.linalg.matrix_rank(eq2)):
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

N, M = (int(i) for i in input().split())
P = [None for i in range(N+1)]
Tree = [list() for i in range(N+1)]
for index in range(M):
	L, R, D = (int(i) for i in input().split())
	Tree[L].append((R, D))
	Tree[R].append((L,-D))

def process(i):
	global P, Tree
	obj = Tree[i]
	if P[i] is None:
		P[i] = 0
	if len(obj) != 0:
		for j, d in obj:
			if P[j] is None:
				P[j] = P[i] + d
				process(j)
			else:
				if P[j] - P[i] != d:
					print("No")
					exit(0)

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

print("Yes")

Submission status: Runtime Error

Solution code:
N, M = (int(i) for i in input().split())
P = [None for i in range(N+1)]
Tree = [list() for i in range(N+1)]
for index in range(M):
	L, R, D = (int(i) for i in input().split())
	Tree[L].append((R, D))
	Tree[R].append((L,-D))

def process(i):
	global P, Tree
	obj = Tree[i]
	if P[i] is None:
		P[i] = 0
	if len(obj) != 0:
		for j, d in obj:
			if P[j] is None:
				P[j] = P[i] + d
				process(j)
			else:
				if P[j] - P[i] != d:
					print("No")
					exit(0)

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

print("Yes")

Submission status: Runtime Error

Solution code:
N, M = (int(i) for i in input().split())
P = [None for i in range(N+1)]
Tree = [list() for i in range(N+1)]
for index in range(M):
	L, R, D = (int(i) for i in input().split())
	Tree[L].append((R, D))
	Tree[R].append((L,-D))

def process(i):
	global P, Tree
	obj = Tree[i]
	if len(obj) != 0:
		if P[i] is None:
			P[i] = 0
		for j, d in obj:
			if P[j] is None:
				P[j] = P[i] + d
				process(j)
			else:
				if P[j] - P[i] != d:
					print("No")
					exit(0)

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

print("Yes")

Submission status: Runtime Error

Solution code:
N, M = (int(i) for i in input().split())
P = [None for i in range(N+1)]
Tree = [list() for i in range(N+1)]
for index in range(M):
	L, R, D = (int(i) for i in input().split())
	Tree[L].append((R, D))
	Tree[R].append((L,-D))

def process(i):
	global P, Tree
	obj = Tree[i]
	if len(obj) != 0:
		if P[i] is None:
			P[i] = 0
		for j, d in obj:
			if P[j] is None:
				P[j] = P[i] + d
				if len(Tree[j]) != 0:
					process(j)
			else:
				if P[j] - P[i] != d:
					print("No")
					exit(0)

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

print("Yes")

Submission status: Runtime Error

Solution code:
import sys
n, m = map(int, raw_input().split())
if m == 0:
    print "Yes"
    sys.exit()
dic = dict()
lis = list()
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    if l > r:
        t = l
        l = r
        r = t
        lis.append((l, r, -d))
    else:
        lis.append((l, r, d))
lis.sort()
un = list()
dic[lis[0][0]] = 0
for l in lis:
    if not l[0] in dic:
        un.append(l)
    else:
        if not l[1] in dic:
            dic[l[1]] = dic[l[0]]+l[2]
        else:
            if not dic[l[1]]-dic[l[0]] == l[2]:
                print "No"
                break
else:
    for l in un:
        if not l[0] in dic:
            if l[1] in dic:
                dic[l[0]] = dic[l[1]]-l[2]
        else:
            if not dic[l[1]]-dic[l[0]] == l[2]:
                print "No"
                break
    else:
        print "Yes"

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
l1 = list(map(int, input().split()))
N = l1[0]
M = l1[1]


per_dis = [ [] for n in range(N+1)]
people = [None] * (N+1)

for n in range(M):
    x = list(map(int, input().split()))
    per_dis[x[0]].append((x[1], x[2]))
    per_dis[x[1]].append((x[0], -x[2]))

if M != 0:
    visited = []
    unvisited = deque([(x[0], 0)])
    people[x[0]] = 0
    while unvisited:
        now = unvisited.popleft()
        for next in per_dis[now[0]]:
            if next[0] not in visited:
                people[next[0]] =  now[1] + next[1]
                unvisited.append((next[0], now[1] + next[1]))
                visited.append(now[0])

for i, x in enumerate(per_dis):
    if x != None:
        for y in x:
            if y[1] < 0:
                if people[y[0]] - people[i] != y[1]:
                    print("No")
                    sys.exit()
            else:
                if people[i] - people[y[0]] != -y[1]:
                    print("No")
                    sys.exit()


print("Yes")

Submission status: Runtime Error

Solution code:
amnesia@amnesia:~/Persistent/procon/atcoder/abc/087$ cat d2.py 
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(a, l, r):
    st = [(l, 0)]
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            return d

        if r in a[i]:
            d += a[i][r]
            a[l][r] = d
            st.append((r, d))
            continue

        for k, v in a[i].items():
            d += v
            a[l][k] = d
            st.append((k, d))

    return -1


def main():
    (n, m) = tuple(map(int, input().split()))
    a = {i:{} for i in range(1, n + 1)}
    for line in sys.stdin:
        (l, r, d) = map(int, line.split())
        pd = dist(a, l, r)
        if pd != -1 and pd != d or dist(a, r, l) != -1:
            print('No')
            sys.exit()
        a[l][r] = d

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(h, l, r):
    st = [(l, 0)]
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            break
        if not h[i][r]:
            st.append((r, d + h[i][r]))
            continue
        for j in range(r):
            if not h[i][j] or i == j:
                continue
            st.append((j, d + h[i][j]))

    return st[-1] if len(st) > 0 else -1


def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    h = [[None] * n] * n
    for lrd in lrds:
        (l, r, d) = lrd
        if not h[l][l]:
            h[l][l] = 0
        if not st[r][r]:
            h[r][r] = 0
        pd = dist(h, l, r)
        if pd != -1 and pd != d:
            print('No')
            sys.exit()
        h[l][r] = d
        h[r][l] = -d

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(h, l, r):
    st = [(l, 0)]
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            break
        if not h[i][r]:
            st.append((r, d + h[i][r]))
            continue
        for j in range(r):
            if not h[i][j] or i == j:
                continue
            st.append((j, d + h[i][j]))

    return st[-1] if len(st) > 0 else 0


def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    h = [[None] * n] * n
    for lrd in lrds:
        (l, r, d) = lrd
        if not h[l][l]:
            h[l][l] = 0
        if not st[r][r]:
            h[r][r] = 0
        pd = dist(h, l, r)
        if pd != -1 and pd != d:
            print('No')
            sys.exit()
        h[l][r] = d
        h[r][l] = -d

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10000)

class G(object):
    def __init__(self, i):
        self.paths = dict()

    def add(self, v, d):
        self.paths[v] = d

    def dist(self, g, s):
        if self is g:
            return s
        if g in self.paths:
            d = g.dist(g, s + self.paths[g])
            self.add(g, d)
            return d
        for k, v in self.paths.items():
            d = k.dist(g, s + v)
            if d >= 0:
                self.add(v, d)
                return d
        return -1

def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    g = dict()
    for lrd in lrds:
        (l, r, d) = lrd
        if l not in g:
            g[l] = G(l)
        if r not in g:
            g[r] = G(r)
        pd = g[l].dist(g[r], 0)
        if pd != -1 and pd != d or g[r].dist(g[l], 0) != -1:
            print('No')
            sys.exit()
        g[l].add(g[r], d)

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

class G(object):
    def __init__(self, i):
        self.paths = dict()

    def add(self, v, d):
        self.paths[v] = d

    def dist(self, g, s):
        if self is g:
            return s
        if g in self.paths:
            d = g.dist(g, s + self.paths[g])
            self.add(g, d)
            return d
        for k, v in self.paths.items():
            d = k.dist(g, s + v)
            if d >= 0:
                self.add(v, d)
                return d
        return -1

def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    g = dict()
    for lrd in lrds:
        (l, r, d) = lrd
        if l not in g:
            g[l] = G(l)
        if r not in g:
            g[r] = G(r)
        pd = g[l].dist(g[r], 0)
        if pd != -1 and pd != d or g[r].dist(g[l], 0) != -1:
            print('No')
            sys.exit()
        g[l].add(g[r], d)

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

class G(object):
    def __init__(self, i):
        self.i = i
        self.a = []

    def add(self, v, d):
        self.a.append((v, d))

    def path(self, j, s):
        if self.i == j:
            return s
        for v in self.a:
            d = v[0].path(j, s + v[1])
            if d >= 0:
                return d
        return -1

def main():
    n, m = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    g = dict()
    for lrd in lrds:
        (l, r, d) = lrd
        if l not in g:
            g[l] = G(l)
        if r not in g:
            g[r] = G(r)
        pd = g[l].path(r, 0)
        if pd != -1 and pd != d or g[r].path(l, 0) != -1:
            print('No')
            sys.exit()
        g[l].add(g[r], d)

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
link = [[] for _ in range(N+1)]
value = [-1 for _ in range(N+1)]

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

searched = set()
q = deque()
for u in range(N+1):
    if u in searched:
        continue
    q.append(u)
    searched.add(u)
    value[u] = 0
    while q:
        x = q.popleft()
        for y, d in link[x]:
            if y not in searched:
                value[y] = value[x] + d
                q.append(y)
                searched.add(y)

for x in range(N+1):
    for y, d in link[x]:
        if value[y] != value[x] + d:
            print('No')
            break
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
link = [[] for _ in range(N+1)]
value = [-1 for _ in range(N+1)]

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

searched = set()
q = deque()
for u in range(N+1):
    if u in searched:
        continue
    q.append(u)
    searched.add(u)
    value[u] = 0
    while q:
        x = q.popleft()
        for y, v in link[x]:
            if y not in searched:
                value[y] = value[x] + d
                q.append(y)
                searched.add(y)

for x in range(N+1):
    for y, d in link[x]:
        if value[y] != value[x] + d:
            print('No')
            break
else:
    print('Yes')

Submission status: Runtime Error

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

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

cache = set(range(1, N+1))

# depth first search
def dfs(graph, start, visited=None):
    global cache  # for checking disconnected
    visited = visited or {}
    visited[start[0]] = start[1]
    cache.remove(start[0])
    for nxt, v in graph[start[0]]:
        nxt_value = start[1] + v
        if nxt in visited:
            if nxt_value != visited[nxt]:
                return False
            continue
        return dfs(graph, (nxt, nxt_value), visited)
    return True

# while len(cache)>0:
#     if not dfs(G, (list(cache)[0], 0)):
#         print('No')
#         break
# else:
#     print('Yes')

if dfs(G, (0, 0)):
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

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

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

cache = set(range(1, N+1))

# depth first search
def dfs(graph, start, visited=None):
    global cache  # for checking disconnected
    visited = visited or {}
    visited[start[0]] = start[1]
    cache.remove(start[0])
    for nxt, v in graph[start[0]]:
        nxt_value = start[1] + v
        if nxt in visited:
            if nxt_value != visited[nxt]:
                return False
            continue
        return dfs(graph, (nxt, nxt_value), visited)
    return True

while len(cache)>0:
    if not dfs(G, (list(cache)[0], 0)):
        print('No')
        break
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
def main():
    """
    N,M:10^6より N^2->NG
    矛盾する情報を見つける
    距離情報の保持

    1-2:1, 2-3:1, 1-3:2 <-OK
    1-2:1, 2-3:1, 1-3:5 <-NG(over)
    1-2:1, 2-3:1, 1-3:1 <-NG(less)
    1-2:1, 2-4:3, 1-3:3 <-OK(2-3:2, 3-4:1)
    1-2:1, 2-4:3, 1-3:5 <-NG

    (Li,Ri,Di)
    人Ri は人Li よりも距離 Di だけ右にいる
    すなわち、xRi − xLi = Di
    Ri > Li のとき(人7の右に人8がいる)処理上問題なし
    Ri < Li のとき(人8の右に人7がいる)場合、
    xLi - xRi = -Di
    """
    N, M = map(int, input().split())
    lrd = [
        tuple(map(int, input().split()))
        for _ in range(M)
    ]

    editorial(N, M, lrd)


def editorial(N, M, lrd):
    import sys
    sys.setrecursionlimit(1e7)

    xs = [None] * N
    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))

    def dfs(i):
        # 辺情報がなければ独立
        for j, d in graph[i]:
            if xs[j] is None:
                xs[j] = xs[i] + d
                f = dfs(j)
                if not f:
                    return False
            elif xs[j] - xs[i] != d:
                # 距離が誤情報
                return False

        return True

    for i, x in enumerate(xs):
        if x is None:
            # root以外は、dfsで木を探索するときに座標確定
            # １回で確定しないときは、独立した木が存在する
            # 他の木とは別で考えて良いので、初期座標は0固定で問題ない
            xs[i] = 0
            f = dfs(i)
            if not f:
                print("No")
                return

    print("Yes")

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    """
    N,M:10^6より N^2->NG
    矛盾する情報を見つける
    距離情報の保持

    1-2:1, 2-3:1, 1-3:2 <-OK
    1-2:1, 2-3:1, 1-3:5 <-NG(over)
    1-2:1, 2-3:1, 1-3:1 <-NG(less)
    1-2:1, 2-4:3, 1-3:3 <-OK(2-3:2, 3-4:1)
    1-2:1, 2-4:3, 1-3:5 <-NG

    (Li,Ri,Di)
    人Ri は人Li よりも距離 Di だけ右にいる
    すなわち、xRi − xLi = Di
    Ri > Li のとき(人7の右に人8がいる)処理上問題なし
    Ri < Li のとき(人8の右に人7がいる)場合、
    xLi - xRi = -Di
    """
    N, M = map(int, input().split())
    lrd = [
        tuple(map(int, input().split()))
        for _ in range(M)
    ]

    editorial(N, M, lrd)


def editorial(N, M, lrd):
    xs = [None] * N
    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))

    def dfs(i):
        # 辺情報がなければ独立
        for j, d in graph[i]:
            if xs[j] is None:
                xs[j] = xs[i] + d
                f = dfs(j)
                if not f:
                    return False
            elif xs[j] - xs[i] != d:
                # 距離が誤情報
                return False

        return True

    for i, x in enumerate(xs):
        if x is None:
            # root以外は、dfsで木を探索するときに座標確定
            # １回で確定しないときは、独立した木が存在する
            # 他の木とは別で考えて良いので、初期座標は0固定で問題ない
            xs[i] = 0
            f = dfs(i)
            if not f:
                print("No")
                return

    print("Yes")

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: UTF-8
from collections import deque
#testdata

class Graph():
  #nodes
  #links
  def __init__(self):
    self.nodes = set()
    self.links = {}
    #nodes -> [tuple(f,cost)]
  
  def readtext(self):
    N,M = map(int,input().split())
    for i in range(M):
      v,w,c = map(int,input().split())
      self.addlink((v,w,c))
    
  
  def addlink(self,link):
    v,w,c = link
    if v not in self.nodes:
      self.nodes.add(v)
      self.links[v] = []
    if w not in self.nodes:
      self.nodes.add(w)
      self.links[w] = []
    
    if v in self.links:
      self.links[v].append((w,c))
      self.links[w].append((v,-c))
    else:
      self.links[v]=[]
      self.links[v].append((w,c))
      self.links[w].append((v,-c))
      
  def addlinks(self,links):
    for link in links:
      self.addlink(link)
  
  def depthfirstsearch(self,so):
    visited = set()
    linq = {}
    #O(links)
    for key in self.links:
      linq[key] = deque(self.links[key])
    #recursive subfunction
    def dfsrec(v,so):
      so.enter()
      visited.add(v)
      while linq[v]:
        cand,cost = linq[v].popleft()
        if cand not in visited:
          so.beforeEnter(v,cand,cost)
          so = dfsrec(cand,so)
      so.exit()
      return so
    
    #call subfunction
    noq = deque(self.nodes)
    while noq:
      x = noq.pop()
      if x not in visited:
        so.enterConnectedPart(x)
        so = dfsrec(x,so)
    return so

class Searcher():
  def __init__(self):
    pass
  def enter(self):
    pass
  def exit(self):
    pass
  def enterConnectedPart(self):
    pass
    
class TimeSearcher(Searcher):
  def __init__(self,graph):
    self.time = 0
    self.parts = 0
    
    self.dist = {} #nodes -> integer
    for node in graph.nodes:
      self.dist[node] = None
  
  def beforeEnter(self,v,cand,cost):
    self.dist[cand] = self.dist[v] + cost
  
  def enter(self):
    self.time += 1
  #def exit(self):
  #  self.time += 1
    
  def enterConnectedPart(self,start):
    self.parts += 1
    self.dist[start] = 0
  def show(self):
    for node in self.dist:
      print(str(node) + " at " + str(self.dist[node]))
  def validate(self,graph):
    for v in graph.links:
      for w,cost in graph.links[v]:
        if self.dist[w] != self.dist[v] + cost:
          return False
    return True

if __name__ == '__main__':
  g = Graph()
  g.readtext()
  so = TimeSearcher(g)
  so = g.depthfirstsearch(so)
  if so.validate(g):
    print("Yes")
  else:
    print("No")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
g = defaultdict(list)

n, m = map(int, input().split())
if m==0:
    print('Yes')
    exit()
for i in range(m):
    l, r, d = map(int, input().split())
    g[l].append((r, d))
    g[r].append((l, -1*d))
    
visited = {}
vv = {k:None for k in g.keys()}
def dfs(v):
    stack = []
    visited[v] = True
    stack.append((v,0))
    while not stack:
        v,w = stack.pop()
        vv[v] = w
        for c,d in g[v]:
            if not visited.get(c, False):
                visited[c] = True
                stack.append((c,w+d))

for f in g.keys():
    if not visited.get(f):
        dfs(f)
        
for k in g.keys():
    v = vv[k]
    for c,w in g[k]:
        if not v + w == vv[c]:
            print('No')
            exit()

print('Yes')

Submission status: Runtime Error

Solution code:
def try_dfs_fill_distance(graph, cur_node, cur_dist_from_origin, distance_cache):
    found_conflicts = False
    for neighbor_node_data in graph[cur_node]:
        neighbor_node, neighbor_distance_from_cur = neighbor_node_data
        neighbor_dist_from_origin = (cur_dist_from_origin + neighbor_distance_from_cur)
        #print("cur_node:{} neighbor_node:{} neighbor_dist:{} origin to {}:{}".format(cur_node, neighbor_node, neighbor_distance_from_cur, neighbor_node, neighbor_dist_from_origin))
        if distance_cache[neighbor_node] == None:
            distance_cache[neighbor_node] = neighbor_dist_from_origin
            found_conflicts = try_dfs_fill_distance(graph, neighbor_node, neighbor_dist_from_origin, distance_cache)
        else:
            if distance_cache[neighbor_node] != neighbor_dist_from_origin:
                #print("{} {} {}".format((distance_cache[neighbor_node] == None), distance_cache[neighbor_node], neighbor_dist_from_origin))
                found_conflicts = True

        if found_conflicts:
            break

    return found_conflicts

if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        l, r, d = list(map(int, input().split()))
        graph[l].append((r, d))
        graph[r].append((l, -d))

    distance_cache = [None for _ in range(n + 1)]
    has_conflict = False
    for i in range(1, len(distance_cache)):
        if distance_cache[i] == None:
            distance_cache[i] = 0
            has_conflict = try_dfs_fill_distance(graph, i, 0, distance_cache)
            if has_conflict:
                break

    print("No" if has_conflict else "Yes")

Submission status: Runtime Error

Solution code:
def try_dfs_fill_distance(graph, cur_node, cur_dist_from_origin, distance_cache):
    found_conflicts = False
    for neighbor_node_data in graph[cur_node]:
        neighbor_node, neighbor_distance_from_cur = neighbor_node_data
        neighbot_dist_from_origin = (cur_dist_from_origin + neighbor_distance_from_cur)
        if distance_cache[neighbor_node] == None:
            distance_cache[neighbor_node] = neighbot_dist_from_origin
            try_dfs_fill_distance(graph, neighbor_node, neighbot_dist_from_origin, distance_cache)
        else:
            if distance_cache[neighbor_node] != neighbot_dist_from_origin:
                found_conflicts = True
                break

    return found_conflicts

if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        l, r, d = list(map(int, input().split()))
        graph[l].append((r, d))
        graph[r].append((l, -d))

    distance_cache = [None for _ in range(n + 1)]
    has_conflict = False
    for i in range(1, len(distance_cache)):
        if distance_cache[i] == None:
            distance_cache[i] = 0
            has_conflict = try_dfs_fill_distance(graph, i, 0, distance_cache)
            if not has_conflict:
                break

    print("No" if has_conflict else "Yes")