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:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc087/tasks/arc090_b

"""
import sys
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline


def solve(data, N):
    scores = [-1] * (N+1)       #  各人の位置
    graphs = [[] for _ in range(N+1)] #  各人が持っている l, r dの情報
    in_degs = [0] * (N+1)       #  トポロジカルソート用の入力次数

    #  入力されたデータから入力次数とグラフ情報を組み立てる
    for l, r, d in data:
        in_degs[r] += 1
        graphs[l].append((r, d))

    pq = []                     #  このキューが空になるまで処理を続ける
    for pos in range(1, N+1):
        if in_degs[pos] == 0:
            heappush(pq, pos)   #  最初は入力次数が0の人を全てキューに登録しておく

    cs = 1                      #  ダミーのスコア
    while pq:
        pos = heappop(pq)
        if scores[pos] < 0:     #  自身に点数が付いていなければ、任意の点数を設定しておく
            scores[pos] = cs
        for r, d in graphs[pos]: #  自身が持っている情報に基づいて、他のノードを点数付けする
            if scores[r] < 0:
                scores[r] = scores[pos] + d
            else:
                if scores[r] != scores[pos] + d: #  他の人によりrが既に点数付けされており、自身の情報と矛盾していれば最終的な答えは'No'になる
                    return 'No'
            in_degs[r] -= 1     #  現在の人からの入力を消去するので、次数を-1する。結果として0になれば次の探索開始ノードとして登録
            if in_degs[r] == 0:
                heappush(pq, r)

    for d in in_degs[1:]:       #  最後まで情報を処理しても入力次数が残っているということは、どこかでループしている。ループは L < R にならないので、'No'を返す
        if d > 0:
            return 'No'
    return 'Yes'


def main(args):
    N, M = map(int, input().split())
    data = []
    for _ in range(M):
        l, r, d = map(int, input().split())
        data.append((l, r, d))
    ans = solve(data, N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def try_dfs_fill_distance(graph, starting_node, distance_cache):
    found_conflicts = False
    traverse_stack = []
    traverse_stack.append((starting_node, 0))

    while traverse_stack:
        node, node_dist_from_origin = traverse_stack.pop()
        if distance_cache[node] == None:
            distance_cache[node] = node_dist_from_origin
            for neighbor_data in graph[node]:
                neighbor_id, neighbor_diff = neighbor_data
                traverse_stack.append((neighbor_id, node_dist_from_origin + neighbor_diff))

        elif distance_cache[node] != node_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:
            has_conflict = try_dfs_fill_distance(graph, i, distance_cache)
            if has_conflict:
                break

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

Submission status: Accepted

Solution code:
def try_dfs_fill_distance(graph, starting_node, distance_cache):
    found_conflicts = False
    traverse_stack = []
    traverse_stack.append((starting_node, 0))

    while traverse_stack:
        node, node_dist_from_origin = traverse_stack.pop()
        if distance_cache[node] == None:
            distance_cache[node] = node_dist_from_origin
            for neighbor_data in graph[node]:
                neighbor_id, neighbor_diff = neighbor_data
                traverse_stack.append((neighbor_id, node_dist_from_origin + neighbor_diff))

        elif distance_cache[node] != node_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_recurse(graph, i, 0, distance_cache)
            has_conflict = try_dfs_fill_distance(graph, i, distance_cache)
            if has_conflict:
                break

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)

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

Solution code:
class UnionFindTree:
    def __init__(self, size):
        self.parent = list(range(size))
        self.dist = [0]*size

    def find_root(self, x):
        if self.parent[x] == x:
            return x, 0
        else:
            self.parent[x], d = self.find_root(self.parent[x])
            self.dist[x] += d
            return self.parent[x], self.dist[x]

    def union(self, x, y, d):
        r1, d1 = self.find_root(x)
        r2, d2 = self.find_root(y)

        if r1 != r2:
            self.parent[r2] = r1
            self.dist[r2] = (d1 - d2) + d
        else:
            if (d2 - d1) != d:
                return False

        return True

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

    tree = UnionFindTree(N)

    for i in range(M):
        l, r, d = map(int, input().split(' '))

        if not tree.union(l-1, r-1, d):
            print('No')
            return

    print('Yes')

main()

Submission status: Accepted

Solution code:
import numpy as np

N, M = tuple(map(int, input().split()))
Ls = np.zeros((M,), dtype=int)
Rs = np.zeros((M,), dtype=int)
Ds = np.zeros((M,), dtype=int)

for i in range(M):
    Ls[i], Rs[i], Ds[i] = tuple(map(int, input().split()))

# debug 1 exit()

Ls = Ls - 1
Rs = Rs - 1

adjacency_list = []
for i in range(N):
    adjacency_list.append([])

for i in range(M):
    adjacency_list[Ls[i]].append((Rs[i], Ds[i]))
    adjacency_list[Rs[i]].append((Ls[i], -Ds[i]))

# print(adjacency_list)

# BFSする
visited = np.zeros(N, dtype=bool)
weights = np.zeros(N, dtype=int)
to_be_visited = []

# debug 2 exit()
pointer = 0
for pointer in range(N):
    if not visited[pointer]:
        to_be_visited.append(pointer)
        while len(to_be_visited) != 0:
            node_index = to_be_visited.pop()
            candidate = adjacency_list[node_index]
            for _i, weight in candidate:
                if not visited[_i]:
                    visited[_i] = True
                    weights[_i] = weights[node_index] + weight
                    to_be_visited.append(_i)

for i in range(M):
    # print("given weights: {}, estimated weights: {}".format(Ds[i],weights[Rs[i]]-weights[Ls[i]]))
    if weights[Rs[i]] - weights[Ls[i]] == Ds[i]:
        # print("passed {} th condition".format(i))
        pass
    else:
        # print("failed {} th condition".format(i))
        print("No")
        exit()
print("Yes")

Submission status: Accepted

Solution code:
def root(x):
    if x == parent[x]:
        return x
    y = root(parent[x])
    dist[x] += dist[parent[x]]
    parent[x] = y
    return y
def unite(x, y, d):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
        dist[py] = dist[x] - dist[y] - d
    else:
        parent[px] = py
        dist[px] = dist[y] - dist[x] + d

n, m = map(int, input().split())
*parent, = range(n)
dist = [0]*n
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1; r -= 1
    if root(l) == root(r):
        if dist[l] - dist[r] != d:
            print("No")
            exit(0)
    else:
        unite(l, r, d)
print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, raw_input().split())
graph = {_: set() for _ in xrange(n + 1)}
in_deg, dist = [0] * (n + 1), [-1] * (n + 1)
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    graph[l].add((r, d))
    in_deg[r] += 1
que = deque([i for i in xrange(n + 1) if not in_deg[i]])
cst = 1
while que:
    stp = que.popleft()  # start_point
    if in_deg[stp] < 0:
        in_deg[stp] = cst
    for v, d in graph[stp]:
        if dist[v] < 0:
            dist[v] = dist[stp] + d
        else:
            if dist[v] != dist[stp] + d:
                print 'No'
                exit()
        in_deg[v] -= 1
        if not in_deg[v]:
            que.append(v)
print 'No' if [_ for _ in in_deg[1:] if _ > 0] else 'Yes'

Submission status: Accepted

Solution code:
def ans():
    NOT_VISITED = -99999
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    visited = [NOT_VISITED for _ in range(N + 1)]

    def dps(graph, start, visited):
        if visited[start] != NOT_VISITED:
            return False
        stuck = [start]
        visited[start] = 0
        while stuck:
            label = stuck.pop()
            for nextnode, distance in graph[label]:
                if visited[nextnode] == NOT_VISITED:
                    stuck.append(nextnode)
                    visited[nextnode] = visited[label] + distance
                elif visited[nextnode] != visited[label] + distance:
                    return True

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

    for i in range(1, N + 1):
        if dps(graph, i, visited):
            return print('No')
    return print('Yes')
# main()
ans()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000002)

def DFS(i, pos, connected, distances):
  if pos[i] == None:
    pos[i] = 0
  size = len(connected[i])
  for j in range(size):
    if pos[connected[i][j]] == None:
      pos[connected[i][j]] = pos[i] + distances[i][j]
      if DFS(connected[i][j], pos, connected, distances) == False:
        return False
    elif pos[connected[i][j]] != pos[i] + distances[i][j]:
      return False
  return True

N, M = map(int, input().split())
pos = [None for i in range(N + 1)]
connected = [[] for i in range(N + 1)]
distances = [[] for i in range(N + 1)]
for i in range(M):
  l, r, d = map(int, input().split())
  connected[l].append(r)
  distances[l].append(d)
  connected[r].append(l)
  distances[r].append(-d)
judge = True
for i in range(1, N + 1):
  if pos[i] == None:
    judge = DFS(i, pos, connected, distances)
    if judge == False:
      break
if judge:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)

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

dist=[None]*(N+1)

def dfs(n):
  for np,nd in mp[n]:
    if dist[np] is None:
      dist[np]=dist[n]+nd
      if not dfs(np):
        return False
    else:
      if dist[np]!=dist[n]+nd:
        return False
  return True
ans=True
for i in range(1,N+1):
  if dist[i] is None:
    dist[i]=0
    if not dfs(i):
      ans=False
      break
if ans:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc087/tasks/arc090_b

"""
import sys
from sys import stdin
from heapq import heappush, heappop
input = stdin.readline




def solve(data, N):
    scores = [-1] * (N+1)
    graphs = [[] for _ in range(N+1)]
    in_degs = [0] * (N+1)

    for l, r, d in data:
        in_degs[r] += 1
        graphs[l].append((r, d))

    pq = []

    for pos in range(1, N+1):
        if in_degs[pos] == 0:
            heappush(pq, pos)

    cs = 1
    while pq:
        pos = heappop(pq)
        if scores[pos] < 0:
            scores[pos] = cs
        for r, d in graphs[pos]:
            if scores[r] < 0:
                scores[r] = scores[pos] + d
            else:
                if scores[r] != scores[pos] + d:
                    return 'No'
            in_degs[r] -= 1
            if in_degs[r] == 0:
                heappush(pq, r)

    for d in in_degs[1:]:
        if d > 0:
            return 'No'
    return 'Yes'


def main(args):
    N, M = map(int, input().split())
    data = []
    for _ in range(M):
        l, r, d = map(int, input().split())
        data.append((l, r, d))
    ans = solve(data, N)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}

for i in range(M):
	L,R,D=map(int,raw_input().split())
	if i==0:start=L
	nl[L].append(R)
	nl[R].append(L)
	cost[(L,R)]=D
	cost[(R,L)]=-D


d=[ None for i in range(N+1) ]
V=[ 0 for i in range(N+1) ]

def dfs(start):
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i]!=1:
				V[i]=1
				q.append(i)
				d[i]=d[v]+cost[(v,i)]
			else:
				if d[i]-d[v]!=cost[(v,i)]:
					print "No"
					quit()

for i in range(1,N+1):
	if V[i]==0:
		dfs(i)
else:
	print "Yes"

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)


def dfs(i, c):
    C[i] = True
    P[i] = c
    for t in G[i]:
        if (C[t[0]] == True):
            continue
        dfs(t[0], c+t[1])
    return


N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
P = [None for _ in range(N+1)]
C = [False for _ in range(N+1)]

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

for i in range(1, N+1):
    if (C[i] == False):
        dfs(i,0)

f = False
for i in range(1, N+1):
    for t in G[i]:
        if ((P[t[0]] - P[i]) != t[1]):
            f = True
if (f):
    print('No')
else:
    print('Yes')

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:
NOT_VISIT = 10**20
N, M = map(int,input().split())
graph = [[] for i in range(N)]

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

visited = [NOT_VISIT for i in range(N)]

def dfs(start):
	global graph, visited

	if visited[start] != NOT_VISIT:
		return True

	stack = [start]
	visited[start] = 0
	while stack:
		label = stack.pop()
		for nextnode, distance in graph[label]:
			if visited[nextnode] == NOT_VISIT:
				stack.append(nextnode)
				visited[nextnode] = visited[label] + distance
			elif visited[nextnode] != visited[label] + distance:
				return False
	return True

res = True
for i in range(N):
	res &= dfs(i)

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

Submission status: Accepted

Solution code:


def dfs(graph, start, visited):
    if visited[start] != -99999:
        return True
    
    stack = [start]
    visited[start] = 0
    while stack:
        label = stack.pop()
        for nextnode, distance in graph[label]:
            if visited[nextnode] == -99999:
                stack.append(nextnode)
                visited[nextnode] = visited[label] + distance
            elif visited[nextnode] != visited[label] + distance:
                return False
    return True

N, M = (int(i) for i in input().split())  

graph = [[] for i in range(N+1)]

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


visited = [-99999 for i in range(N+1)]

flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

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

Submission status: Accepted

Solution code:
def d_People_on_a_Line(N, M, P):
    if M == 0:
        return 'Yes'

    adj = [[] for _ in range(N)]  # 隣接リスト
    for l, r, d in P:
        adj[l - 1].append([r - 1, d])
        adj[r - 1].append([l - 1, -d])

    dist = [None for _ in range(N)]
    for i in range(N):  # グラフが非連結なこともあるので、全頂点を始点として試す
        if dist[i] is not None:
            # 値が決定済み
            continue
        stack = [i]
        dist[i] = 0  # 始点の距離は0
        while stack:
            v = stack.pop()  # 訪れる頂点
            for to, cost in adj[v]:
                if dist[to] is None:
                    # 頂点toが未決定なら、そこを次に訪れる頂点とする
                    stack.append(to)
                    dist[to] = dist[v] + cost
                elif dist[to] != dist[v] + cost:
                    # 値が決定済みの頂点に合流し、
                    # 与えられた情報と矛盾した
                    return 'No'
    return 'Yes'  # 全頂点で矛盾しなかった

N,M = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(M)]
print(d_People_on_a_Line(N, M, P))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200002)

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

N, M = map(int, input().split())
x = [None] * N
G = [[] for _ in range(N)]
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append([R, D])
    G[R].append([L, -D])
ans = True
for i in range(N):
    if x[i] is None:
        x[i] = 0
        if not dfs(i):
            ans = False
print(('No', 'Yes')[ans])

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, size):
        self.parent = list(range(size))
        self.dist = [0] * size

    def find_root(self, x):
        if self.parent[x] == x:
            return x, 0
        else:
            self.parent[x], d = self.find_root(self.parent[x])
            self.dist[x] += d
            return self.parent[x], self.dist[x]

    def union(self, x, y, d):
        r1, d1 = self.find_root(x)
        r2, d2 = self.find_root(y)
        if r1 != r2:
            self.parent[r2] = r1
            self.dist[r2] = (d1 - d2) + d
        else:
            if (d2 - d1) != d:
                return False
        return True

def main():
    n, m = map(int, input().split())
    tree = UnionFindTree(n+1)
    for i in range(m):
        l, r, d = map(int, input().split())
        if not tree.union(l, r, d):
            print('No')
            return
    print('Yes')

main()

Submission status: Accepted

Solution code:
import collections
from pprint import pprint as pp

N,M = tuple(map(int, input().split()))
LRD = collections.defaultdict(list)
Lset = set()
Rset = set()
for _ in range(M):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  LRD[l].append((r,d))
  Lset.add(l)
  Rset.add(r)

n = [ None for _ in range(N) ]

deq = collections.deque()

def func(l):
  lst = LRD.pop(l,[])
  for r,d in lst:
    if n[l] != None:
      d2 = n[l] + d
    else:
      n[l] = 0
      d2 = d
    if n[r] not in (d2, None):
      return True
    n[r] = d2
    deq.append(r)
  return False

def func2():
  lst = Lset-Rset
  for l in lst:
    n[l] = 0
    deq.append(l)
  while deq:
    l = deq.popleft()
    if l in LRD:
      if func(l):
        return True
  deq.extend(LRD.keys())
  while deq:
    l = deq.popleft()
    if l in LRD:
      if func(l):
        return True
  return False

if func2():
  print('No')
else:
  print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
edges = {}
connections = {}
for _ in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    assert (l, r) not in edges
    assert (r, l) not in edges
    edges[l, r] = d

    if l not in connections:
        connections[l] = set()
    if r not in connections:
        connections[r] = set()
    connections[l].add(r)
    connections[r].add(l)


def solve():
    fixed = [None] * N
    undone = set(range(N))

    while undone:
        start = undone.pop()
        undone.add(start)
        queue = deque()
        queue.append(start)

        while queue:
            x = queue.popleft()
            if x not in undone:
                continue
            undone.remove(x)
            if x not in connections:
                continue

            for y in connections[x]:
                if y in undone:
                    queue.append(y)
                if (x, y) in edges:
                    if fixed[x] is None:
                        if fixed[y] is None:
                            fixed[x] = 0
                            fixed[y] = edges[x, y]
                        else:
                            fixed[x] = fixed[y] - edges[x, y]
                    else:
                        if fixed[y] is None:
                            fixed[y] = fixed[x] + edges[x, y]
                        else:
                            if fixed[x] + edges[x, y] != fixed[y]:
                                return False
                elif (y, x) in edges:
                    if fixed[y] is None:
                        if fixed[x] is None:
                            fixed[y] = 0
                            fixed[x] = edges[y, x]
                        else:
                            fixed[y] = fixed[x] - edges[y, x]
                    else:
                        if fixed[x] is None:
                            fixed[x] = fixed[y] + edges[y, x]
                        else:
                            if fixed[y] + edges[y, x] != fixed[x]:
                                return False

    xmin = xmax = None
    for i in range(N):
        if fixed[i] is None:
            continue
        if xmin is None:
            xmin = xmax = fixed[i]
        else:
            xmin = min(xmin, fixed[i])
            xmax = max(xmax, fixed[i])
    if xmax is not None and xmin is not None:
        if 10 ** 9 < xmax - xmin:
            return False
    return True


print('Yes' if solve() else 'No')

Submission status: Runtime Error

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

class UnionfindWithWeight():
    def __init__(self, n):
        self.dist    = [0]  * (n+1)
        self.ranks   = [0]  * (n+1)
        self.parents = [-1] * (n+1)
    def find_root(self, x):
        if self.parents[x] < 0:
            return self.dist[x], x
        else:
            tmp = self.find_root(self.parents[x])
            self.dist[x]    += tmp[0]
            self.parents[x] =  tmp[1]
            return self.dist[x], self.parents[x]
    def union(self, x, y, dist):
        x_root = self.find_root(x)[1]
        y_root = self.find_root(y)[1]
        diff = dist + self.dist[x] - self.dist[y]
        if x_root == y_root and diff != 0:
            # print("This dist is invalid.", flush=True)
            return -1
        if self.ranks[y_root] > self.ranks[x_root]:
            x_root ,y_root = y_root, x_root
            diff =- diff
        self.parents[y_root] = x_root
        self.dist[y_root] = diff
        if self.ranks[y_root] == self.ranks[x_root]:
            self.ranks[x_root] += 1

v=UnionfindWithWeight(n)
for i in range(m):
    l, r, d = list(map(int, input().split()))
    if v.union(l,r,d) == -1:
        print('No')
        import sys
        sys.exit()

print('Yes')

Submission status: Runtime Error

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

class UnionfindWithWeight():
    def __init__(self, n):
        self.dist    = [0]  * (n+1)
        self.ranks   = [0]  * (n+1)
        self.parents = [-1] * (n+1)
    def find_root(self, x):
        if self.parents[x] < 0:
            return self.dist[x], x
        else:
            tmp = self.find_root(self.parents[x])
            self.dist[x]    += tmp[0]
            self.parents[x] =  tmp[1]
            return self.dist[x], self.parents[x]
    def union(self, x, y, dist):
        x_root = self.find_root(x)[1]
        y_root = self.find_root(y)[1]
        diff = dist + self.dist[x] - self.dist[y]
        if x_root == y_root and diff != 0:
            return False
        if self.ranks[y_root] > self.ranks[x_root]:
            x_root ,y_root = y_root, x_root
            diff =- diff
        self.parents[y_root] = x_root
        self.dist[y_root] = diff
        if self.ranks[y_root] == self.ranks[x_root]:
            self.ranks[x_root] += 1

v=UnionfindWithWeight(n)
lrd = []
for i in range(m):
    l, r, d = list(map(int, input().split()))
    if v.union(l,r,d):
        print('No')
        import sys
        sys.exit()

print('Yes')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n, m = list(map(int, input().split()))

graph = [[] for i in range(n)]
for i in range(m):
    l, r, d = list(map(int, input().split()))

    graph[l-1].append([r-1, d])
    graph[r-1].append([l-1, -d])
# print(graph)


def dfs(s):
    for t, d in graph[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


x = [None]*n
ans = True
for i in range(n):
    if x[i] is None:
        x[i] = 0
        if not dfs(i):
            ans = False

print(('No', 'Yes')[ans])

Submission status: Runtime Error

Solution code:
# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
d = defaultdict(int)
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, d in es[v]:
        if value[i] == INF:
            value[i] = value[v] + d
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")

Submission status: Runtime Error

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

import numpy as np
Graph = np.full((N,N), np.inf)
for l,r,d in LRD:
    Graph[r-1,l-1] = d
    Graph[l-1,r-1] = -d
import scipy.sparse.csgraph as csg
try:
    Graph = csg.johnson(Graph)
    for l,r,d in LRD:
        if Graph[r-1,l-1] != d or Graph[l-1,r-1] != -d:
            ans = 'No'
            break
    else:
        ans = 'Yes'
except csg.NegativeCycleError:
    ans = 'No'
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((-c,u))
vals = [None] * n
def dijkstra(start):
    h = [start]
    vals[start] = 0
    ans = True
    while h:
        u = h.pop()
        for d, v in ns[u]:
            if vals[v] is None:
                vals[v] = vals[u]+d
                h.append(v)
            else:
                if vals[v]!=val+d:
                    return False
    return ans

for start in range(n):
    if vals[start] is not None:
        continue
    res = dijkstra(start)
    if not res:
        print("No")
        break
else:
    print("Yes")