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 = (int(i) for i in input().split())
y,z,ans = [[] for i in range(n+1)],[None for i in range(n+1)],"Yes"
for num in range(m):
	i,j,k = (int(i) for i in input().split())
	y[i].append([j,k])
	y[j].append([i,-k])
for i in range(1,n+1):
	if z[i] == None:
		z[i],q = 0,[i]
		while q:
			p = q.pop()
			for j,k in y[p]:
				if z[j] == None:
					q.append(j)
					z[j] = z[p]+k
for i in range(1,n+1):
	for j,k in y[i]:
		if z[i]+k != z[j]: ans = "No"
print(ans)

Submission status: Accepted

Solution code:
class WeightUnionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)
        self.weight=[0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            r = self.find(self.par[x])
            self.weight[x]+=self.weight[self.par[x]]
            self.par[x]=r
            return self.par[x]
        
    def weighted(self,x):
        self.find(x)
        return self.weight[x]
    
    def union(self,x,y,w):#weight(y) = weight(x) + w となるように x と y をマージする
        w += self.weighted(x)
        w -= self.weighted(y)
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
            self.weight[px]=-w
        else:
            self.par[py]=px
            self.weight[py] = w
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
    
    def diff(self,x,y):
        return self.weighted(y)-self.weighted(x)
    
N,M = map(int,input().split())
Tree = WeightUnionfindtree(N)
ans = 'Yes'
for i in range(M):
    L,R,D = map(int,input().split())
    if Tree.connect(L-1,R-1):
        if Tree.diff(L-1,R-1)!=D:
            ans = 'No'
    else:
        Tree.union(L-1,R-1,D)
print(ans)

Submission status: Accepted

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

parent = [i for i in range(N+1)]
distance = [0 for i in range(N+1)]
depth = [1 for i in range(N+1)]

def root(x):
    if x == parent[x]:
        return x
    else:
        return root(parent[x])

def to_root(x):
    if x == parent[x]:
        return 0
    else:
        return distance[x] + to_root(parent[x])

for _ in range(M):
    L, R, D = map(int, input().split())
    # print("distance", D, to_root(L), to_root(R))
    # print("root    ", root(L), root(R))
    # print(_, L, R, D)
    if root(L) == root(R):
        l = to_root(L)
        r = to_root(R)
        # print("distance", D, l, r)
        # print("root    ", root(L), root(R))
        if D != r-l:
            # print(parent)
            # print(distance)
            print("No")
            exit()
    else:
        rootL = root(L)
        rootR = root(R)
        if depth[rootL] < depth[rootR]:
            L,R = R,L
            D = -D
        rootL = root(L)
        rootR = root(R)
        parent[rootR] = rootL
        distance[rootR] = -to_root(R)+to_root(L)+D
        depth[rootL] = max(rootL, depth[rootR]+1)
print("Yes")

Submission status: Accepted

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

g = [[] for _ in range(n+1)]
cood= [None for _ in range(n+1)]


def dfs(start):
    if cood[start] != None:
        return True
    stack = [start]
    cood[start] = 0
    while stack:
        v = stack.pop()
        for to, dist in g[v]:
            if cood[to] == None:
                stack.append(to)
                cood[to] = cood[v] + dist
            elif cood[v] + dist != cood[to]:
                return False
    return True

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

flag = True
for i in range(1,n+1):
    if not dfs(i):
        flag = False
if flag:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
g = [[] for _ in range(0,n)]
x = [None] * n
ans = "Yes"
for i in range(0,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(0,n):
    if x[i] is not None:
        continue
    x[i] = 0
    q = [i]
    while len(q) > 0:
        qq = q.pop()
        for r,d in g[qq]:
            if x[r] is None:
                q.append(r)
                x[r] = x[qq] + d
for i in range(0,n):
    for r,d in g[i]:
        if x[i] + d != x[r]:
            ans = "No"
            break
print(ans)

Submission status: Accepted

Solution code:
import queue,sys
# 解説読んだ後
N,M=map(int,input().split())
# networkを作る
G={}
LRD=[]
for i in range(1,N+1):
    G[i]={}
for i in range(M):
    l,r,d=map(int,input().split())
    LRD.append((l,r,d))
    G[l][r]=d
    G[r][l]=-d
if M==0:
    print("Yes")
    sys.exit()
notvisit=set(range(1,N+1))
Q=queue.Queue()
x={}
while notvisit:
    current=notvisit.pop()
    Q.put(current)
    x[current]=0
    while Q.qsize():
        nex=Q.get()
        for k,v in G[nex].items():
            if k in x:
                if x[k]!= x[nex]+G[nex][k]:
                    print("No")
                    sys.exit()
            else:
                x[k]=x[nex]+G[nex][k]
                Q.put(k)
                notvisit.remove(k)
print("Yes")

Submission status: Accepted

Solution code:
def solve():
    n, m = map(int, raw_input().split())
    edge = {v:[] for v in range(1,n+1)}
    dist = {}
    for i in range(m):
        l, r, d = map(int, raw_input().split())
        edge[l].append(r)
        edge[r].append(l)
        dist[l,r] = d
        dist[r,l] = -d
    return "Yes" if ok(edge, dist, n) else "No"

def ok(edge, dist, n):
    used = [False] * (n+1)
    used[0] = True
    path = {}
    for s in range(1, n+1):
        if used[s]:
            continue
        que = [s]
        path[s, s] = 0
        used[s] = True
        while que:
            u = que.pop()
            for v in edge[u]:
                d = path[s,u] + dist[u,v]
                if not used[v]:
                    path[s,v] = d
                    que.append(v)
                    used[v] = True
                elif d != path[s,v]:
                    return False
    return True

print solve()

Submission status: Accepted

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

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

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

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

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

def main():
    n, m = map(int, input().split())
    wuf = WeightedUnionFind(n)
    for _ in range(m):
        l, r, d = map(int, input().split())
        if not wuf.same(l, r):
            wuf.union(l, r, d)
        else:
            if wuf.diff(l, r) != d:
                print('No')
                return
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]),int(input_raw[1])]
    adj_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [L, R, D] = [int(input_raw[0]),int(input_raw[1]),int(input_raw[2])]
        if  L not in adj_list :
            adj_list[L] = [(R, D)]
        else:
            adj_list[L].append((R, D))
        if R not in adj_list :
            adj_list[R] = [(L, -D)]
        else:
            adj_list[R].append((L, -D))


    node_list = deque([])
    done_set = {}
    is_ok = True
    for L in adj_list:
        if is_ok == False:
            break
        if L not in done_set:
            node_list.append(L)
            done_set[L] = 0

            while 1:
                if len(node_list) <= 0:
                    break
                nd = node_list.popleft()
                for adj in adj_list[nd]:

                    if adj[0] not in done_set:
                        node_list.append(adj[0])
                        done_set[adj[0]] = done_set[nd] + adj[1]
                    else:
                        if(done_set[adj[0]] != done_set[nd] + adj[1]):
                            is_ok = False
                            break;

    if is_ok == True:
        print "Yes"
    else:
        print "No"







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200002)


def dfs(start, edges, nodes):
    for adj_node, distance in edges[start].items():
        # まだ訪れていない隣接ノード
        if nodes[adj_node] is None:
            nodes[adj_node] = nodes[start] + distance
            # adj_nodeを開始位置にしてまだ訪れていないノードを探索する
            # 探索中にノード値とエッジの関係性が一致しなくなればFalse
            if not dfs(adj_node, edges, nodes):
                return False
        # 既に訪れた隣接ノード
        else:
            if nodes[adj_node] - nodes[start] != distance:
                return False

    return True


if __name__ == '__main__':
    N, M = map(int, input().split())
    if M == 0:
        print("Yes")
        exit(0)

    Ls, Rs, Ds = zip(*[list(map(int, input().split())) for _ in range(M)])

    # N, M = 10, 3
    # Ls, Rs, Ds = zip(*[[8, 7, 100],
    #                    [7, 9, 100],
    #                    [9, 8, 100]])

    edges = {i: dict() for i in range(N)}

    for L, R, D in zip(Ls, Rs, Ds):
        edges[L - 1][R - 1] = D
        edges[R - 1][L - 1] = -D

    nodes = [None] * N

    valid_list = []
    for start in range(N):
        if nodes[start] is None:
            nodes[start] = 0
            # ノード値とエッジの関係性が一致しなくなればfalse
            valid_list.append(dfs(start, edges, nodes))

    if all(valid_list):
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n+1) ]
dist=[None for i in range(n+1)]
dist[0]=0
result=[True]

for i in range(m):
    l,r,d=(int(i) for i in input().split())
    graph[l].append((r,-d))
    graph[r].append((l,d))
def haba(i):
    if dist[i]== None:
        stack=[]
        dist[i]=0
        stack.append(i)
        while len(stack)!=0 :
            l=stack.pop()
            for r,d in graph[l]:
                b=dist[l]+d
                if dist[r]==None :
                    dist[r]=b
                    stack.append(r)
                elif dist[r]!=b:
                     result[0]=False
                     return
        return 
    else:
        return 

for i in range(n+1):
    haba(i)
if result[0]:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
xrd = [[] for i in range(N)]
x = [None]*N


def check(s):
    global xrd,x
    for t, d in xrd[s]:
        if x[t] is None:
            x[t] = x[s] + d
            check(t)
        else:
            if x[t] != x[s] + d:
                print("No")
                exit()


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

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


print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
x = [None] * N

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

def dfs(s):
    global x, G
    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: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
x = [None] * N

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

def dfs(s):
    global x, G
    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: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
x = [None] * (N)

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

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: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)

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

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: Accepted

Solution code:
def check(graph):
    import queue
    N = len(graph)
    tmp_position = [None] * N
    for i in range(N):
        if tmp_position[i] is None:
            tmp_position[i] = 0
            qu = queue.Queue()
            qu.put(i)
            while not qu.empty():
                now = qu.get()
                now_dist = tmp_position[now]
                for nxt, nxt_dist in graph[now]:
                    if tmp_position[nxt] is None:
                        tmp_position[nxt] = now_dist + nxt_dist
                        qu.put(nxt)
                    elif tmp_position[nxt] != now_dist + nxt_dist:
                        return False
    return True


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))
print("Yes" if check(graph)else "No")

Submission status: Accepted

Solution code:
from collections import deque

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

X = [0 for _ in range(N+1)]
edges = [[] for _ in range(N+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: Accepted

Solution code:
from queue import Queue
import sys

inf = float("inf")
N, M = list(map(int, input().split()))
dist = [[] for x in range(N+1)]
value = [inf for x in range(N+1)]

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

for i in range(1, N+1):
    if value[i] != inf: continue
    
    value[i] = 0
    q = Queue()
    q.put(i)
    while not q.empty():
        tmp = q.get()
        for x in dist[tmp]:
            nxt = x[0]
            nxt_val = value[tmp] + x[1]
            if value[nxt] != inf:
                if value[nxt] == nxt_val: continue
                print("No")
                sys.exit()
            value[nxt] = nxt_val
            q.put(nxt)
print("Yes")

Submission status: Accepted

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[now]:
            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+1)]
    people = [None] * (N+1)

    #グラフの作成
    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(1,N+1):
        bfs(i, graph, people)

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

Submission status: Accepted

Solution code:


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

adj = [ [] for i in range(N+1)]
distance = [-1 for i in range(N+1)]
visited = [1] + [0 for i in range(N)]
ans = True

def dfs(node):
	stack = [node]
	visited[node] = 1
	if(distance[node] == -1):
		distance[node] = 0
	while(len(stack)):
		v = stack.pop()
		p = distance[v]
		for n, d in adj[v]:
			if(visited[n] == 0):
				distance[n] = p + d
				visited[n] = 1
				stack.append(n)
			else:
				if(distance[n] != p + d):
					return False
	return True


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

for v in range(1, N+1):
	if(visited[v] == 1):
		continue
	if(not dfs(v)):
		ans = False
		break


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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(x, graph, people):
    if people[x] is not None:
        return
    unvisited = deque([x])
    people[x] = 0
    while unvisited:
        now = unvisited.popleft()
        for next, d in graph[now]:
            if people[next] is None:
                people[next] =  people[now] + d
                unvisited.append(next)

def main():
    N, M = list(map(int, input().split()))

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

    for n 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(1, N+1):
        bfs(i, graph, people)

    for i in range(1, N+1):
        for j, d in graph[i]:
            if people[j] - people[i] != d:
                print("No")
                exit()
    else:
        print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

def determine(i):
	if P[i] is not None:
		return
	P[i] = 0
	stack = [i]
	while len(stack) != 0:
		I = stack.pop()
		for j, d in Graph[I]:
			if P[j] is None:
				P[j] = P[I] + d
				stack.append(j)

def check(i):
	for j, d in Graph[i]:
		if P[j] - P[i] != d:
			print("No")
			exit(0)

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

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

print("Yes")

Submission status: Accepted

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

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i] is not None:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if x[u] is None:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N, M = map(int, input().split())
    link = [[] for _ in range(N+1)]
    value = [0 for _ in range(N+1)]

    for _ in range(M):
        l, r, d = map(int, input().split())
        link[l].append((r, d))
        link[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

        # search
        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)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: UTF-8
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())
  link[L].append((R,D))
  link[R].append((L,-D))

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

#verification
for v in range(N+1):
  for w,d in link[v]:
    if value[w] != value[v] + d:
      print("No")
      exit()
print("Yes")

Submission status: Accepted

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(10 ** 7)

    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: Accepted

Solution code:
import sys


def main():
    n, m = map(int, sys.stdin.readline().split())
    g = [[] for i in range(n)]
    deg = [0] * n
    for i in range(m):
        l, r, d = map(int, sys.stdin.readline().split())
        g[l - 1].append((r - 1, d))
        deg[r - 1] += 1
    dis = [-1] * n
    for i in range(n):
        if deg[i]:
            continue
        stack = list([i])
        dis[i] = 0
        while len(stack):
            v = stack[-1]
            stack.pop()
            for u, d in g[v]:
                if dis[u] == -1:
                    dis[u] = dis[v] + d
                    stack.append(u)
    for v in range(n):
        for u, d in g[v]:
            if dis[v] + d != dis[u]:
                print('No')
                return
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def main():
    n, m = map(int, sys.stdin.readline().split())
    g = [[] for i in range(n)]
    deg = [0] * n
    lines = sys.stdin.read().splitlines()
    for line in lines:
        l, r, d = map(int, line.split())
        g[l - 1].append((r - 1, d))
        deg[r - 1] += 1
    dis = [-1] * n
    for i in range(n):
        if deg[i]:
            continue
        stack = list([i])
        dis[i] = 0
        while len(stack):
            v = stack[-1]
            stack.pop()
            for u, d in g[v]:
                if dis[u] == -1:
                    dis[u] = dis[v] + d
                    stack.append(u)
    for v in range(n):
        for u, d in g[v]:
            if dis[v] + d != dis[u]:
                print('No')
                return
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def main():
    n, m = map(int, sys.stdin.readline().split())
    g = [[] for i in range(n)]
    for i in range(m):
        l, r, d = map(int, sys.stdin.readline().split())
        g[l - 1].append((r - 1, d))
        g[r - 1].append((l - 1, -d))
    dis = [0] * n
    visited = [False] * n
    for i in range(n):
        if visited[i]:
            continue
        stack = list([i])
        visited[i] = True
        while len(stack):
            v = stack[-1]
            stack.pop()
            for u, d in g[v]:
                if not visited[u]:
                    dis[u] = dis[v] + d
                    stack.append(u)
                    visited[u] = True
    for v in range(n):
        for u, d in g[v]:
            if dis[v] + d != dis[u]:
                print('No')
                return
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    lines = sys.stdin.read().splitlines()
    for i in range(m):
        l, r, d = map(int, lines[i].split())
        g[l - 1].append((r - 1, d))
        g[r - 1].append((l - 1, -d))
    dis = [0] * n
    visited = [False] * n
    for i in range(n):
        if visited[i]:
            continue
        stack = list([i])
        visited[i] = True
        while len(stack):
            v = stack[-1]
            stack.pop()
            for u, d in g[v]:
                if not visited[u]:
                    dis[u] = dis[v] + d
                    stack.append(u)
                    visited[u] = True
    for v in range(n):
        for u, d in g[v]:
            if dis[v] + d != dis[u]:
                print('No')
                return
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    g = [[] for i 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))
    dis = [0] * n
    visited = [False] * n
    for i in range(n):
        if visited[i]:
            continue
        stack = list([i])
        visited[i] = True
        while len(stack):
            v = stack[-1]
            stack.pop()
            for u, d in g[v]:
                if not visited[u]:
                    dis[u] = dis[v] + d
                    stack.append(u)
                    visited[u] = True
    for v in range(n):
        for u, d in g[v]:
            if dis[v] + d != dis[u]:
                print('No')
                return
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

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 len(stack)!=0:
        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')