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:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())

            


    def no_contradict_p(info):
        visited = [False] * n
        dist_list = [None] * n

        def bfs_and_check_no_contradict(start):
            dist_list[start] = 0
            q = deque([start])
            while q:
                u = q.popleft()
                if not visited[u]:
                    visited[u] = True
                    for v, dist in info[u]:
                        if dist_list[v] is None:
                            dist_list[v] = dist_list[u] + dist
                        elif dist_list[v] != dist_list[u] + dist:
                            return False
                    for v, dist in info[u]:
                        if not visited[v]:
                            q.append(v)
            return True
        
        for i in range(n):
            if not visited[i]:
                if not bfs_and_check_no_contradict(i):
                    return False
        return True


    
    n, m = mi()
    info = [[] for _ in range(n)]
    for _ in range(m):
        l, r, dist = mi_0()
        dist += 1
        info[l].append((r, dist))
        info[r].append((l, -dist))
    
    print('Yes') if no_contradict_p(info) else print('No')



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
par=[-1]*n
wei=[0]*n

#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]

#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)


for i in range(m):
    l,r,d=map(int,input().split())
    if same(l-1,r-1):
        if d!=diff(l-1,r-1):
            print('No')
            sys.exit()
    else:
        unite(l-1,r-1,d)

print('Yes')

Submission status: Accepted

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

graph = [[] for i in range(N)]
left = set()
right = set()
for i in range(M):
  l, r, d = map(int, input().split())
  l -= 1; r -= 1
  graph[l].append((r, d))
  graph[r].append((l, -d))
  left.add(l); right.add(r)

root = left - right
if M and len(root) == 0:
  print('No')
  quit()

X = [None] * N
while root:
  node = root.pop()
  X[node] = 0
  stack = [node]
  while stack:
    node = stack.pop()
    while graph[node]:
      child, d = graph[node].pop()
      if X[child] is None:
        X[child] = X[node] + d
        stack.append(child)
      elif X[child] != X[node] + d:
        print('No')
        quit()

print('Yes')

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]
    
n,m = map(int,input().split())
lrd = [[int(i) for i in input().split()] for j in range(m)]

ki = WeightedUnionFind(n)

for i in range(m):
    if ki.same(lrd[i][0],lrd[i][1]):
        if ki.diff(lrd[i][0],lrd[i][1]) != lrd[i][2]:
            print('No')
            exit()
    else:
        ki.union(lrd[i][0],lrd[i][1],lrd[i][2])
    
print('Yes')

Submission status: Accepted

Solution code:
# potential union findの問題と聞いて
class PotentialUnionFind:
    # あり本実装
    # rankとrootの配列を1つで賄う方法
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
        self.weight = [0] * n

    # 根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            px = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = px
            return px

    # 頂点からのpotential
    def weight(self, x):
        self.find(x)
        return self.weight[x]

    # 同じかどうかの判定
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.find(x)

    # 　2つの集合の合体
    # 重みが大きい方に小さい方をつけるようにする
    def unite(self, x, y, w):
        w += self.weight[x] - self.weight[y]
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False

        if self.par[x] > self.par[y]:
            x, y = y, x
            w = -w
        self.par[x] += self.par[y]
        self.par[y] = x
        self.weight[y] = w
        return True

    def diff(self, x, y):
        return self.weight[y] - self.weight[x]


n, m = map(int, input().split())
PUF = PotentialUnionFind(n)
flag = 0
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if PUF.is_same(l, r):
        if abs(PUF.diff(l, r)) == d:
            continue
        else:
            flag = 1
    else:
        PUF.unite(l, r, d)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


class WeightedUnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.parents = [-1] * n_nodes

        # 親への重みを管理
        self.weights = [0] * n_nodes

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            parent = self.find(self.parents[x])
            self.weights[x] += self.weights[self.parents[x]]
            self.parents[x] = parent
            return parent

    # xからyへの重みがw
    def unite(self, x, y, w):
        w += self.weights[x]
        w -= self.weights[y]
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
            w *= -1

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.weights[y] = w
        return

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return -self.parents[self.find(x)]

    def get_weight(self, x, y):
        return self.weights[y] - self.weights[x]


def main():
    N, M = map(int, input().split())
    tree = WeightedUnionFind(N)
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1

        if tree.is_same(L, R):
            if tree.get_weight(L, R) == D:
                continue
            else:
                print("No")
                return
        else:
            tree.unite(L, R, D)

    print("Yes")
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, sys.stdin.readline().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, *args, **kwargs):
	return np.fromiter(inputs(type, *args, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, *args, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, *args, **kwargs)
	return data

class IntAddition (object):
	'''整数の加法'''
	def operate(self, x, y):
		return x + y
	@property
	def identity(self):
		return 0
	def cancel(self, x, y):
		return x - y
	def invert(self, x):
		return -x
	def accumulate(self, x, count):
		return x * count

class UnionFindNode (object):
	__slots__ = [
		'parent_index',
		'size',
		'difference_from_parent'
	]
	
	def __init__(self, index : int, potential_identity):
		self.parent_index = index
		self.size = 1
		self.difference_from_parent = potential_identity

class UnionFind (object):
	'''重み付きUnion-Find木'''
	def __init__(
			self,
			num_nodes=0,
			potential_abelian=IntAddition()):
		self.nodes = []
		self.op = potential_abelian
		
		self.extend(num_nodes)
	
	def append(self):
		self.nodes.append(
			UnionFindNode(len(self.nodes), self.op.identity)
		)
		
	def extend(self, num_nodes):
		self.nodes.extend(
			UnionFindNode(i, self.op.identity)
			for i in range(num_nodes)
		)
	
	def root(self, index : int):
		x = self.nodes[index]
		
		while x.parent_index != index:
			parent = self.nodes[x.parent_index]
			x.difference_from_parent = self.op.operate(
				x.difference_from_parent,
				parent.difference_from_parent
			)
			index = x.parent_index = parent.parent_index
			x = self.nodes[index]
		
		return index
	
	def difference_from_root_to(self, index : int):
		x = self.nodes[index]
		potential = x.difference_from_parent
		
		while x.parent_index != index:
			parent = self.nodes[x.parent_index]
			potential = self.op.operate(
				potential,
				parent.difference_from_parent
			)
			index = x.parent_index
			x = self.nodes[index]
		
		return potential
		
	def size(self, index : int):
		return self.nodes[self.root(index)].size
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(
			self.difference_from_root_to(y),
			self.difference_from_root_to(x)
		)
	
	def unite(self, x, y, difference=None) -> bool:
		if difference is None:
			difference = self.op.identity
		
		x, px = self.root(x), self.difference_from_root_to(x)
		y, py = self.root(y), self.difference_from_root_to(y)
		if x == y:
			return difference == self.op.cancel(py, px)
		
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		
		x_node = self.nodes[x]
		y_node = self.nodes[y]
		x_node.size += y_node.size
		y_node.parent_index = x
		y_node.difference_from_parent = difference
		
		return True
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)



N, M = inputs(int)
uf = UnionFind(num_nodes=N)

valid = True
for i in range(M):
	L, R, D = inputs(int)
	L -= 1
	R -= 1
	
	valid = valid and uf.unite(L, R, D)

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

Submission status: Accepted

Solution code:
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, input().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, *args, **kwargs):
	return np.fromiter(inputs(type, *args, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, *args, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, *args, **kwargs)
	return data

class Repeat (object):
	__slots__ = [
		'element',
		'times'
	]
	
	def __init__(self, element, times : int):
		self.element = element
		self.times = int(times)
	
	def __len__(self):
		return self.times
	
	def __iter__(self):
		return iter(self.element for _ in range(self.times))

def repeat(element, times : int):
	return Repeat(element, times)

class IntAddition (object):
	'''整数の加法'''
	def operate(self, x, y):
		return x + y
	@property
	def identity(self):
		return 0
	def cancel(self, x, y):
		return x - y
	def invert(self, x):
		return -x
	def accumulate(self, x, count):
		return x * count

class UnionFind (object):
	'''重み付きUnion-Find木'''
	def __init__(
			self,
			num_nodes=0,
			abelian_operator=IntAddition()):
		self.parent = []
		self.potential = []
		self.op = abelian_operator
		
		self.extend(num_nodes)
	
	def append(self):
		self.parent.append(-1)
		self.potential.append(self.op.identity)
	
	def extend(self, num_nodes):
		self.parent.extend(repeat(-1, num_nodes))
		self.potential.extend(repeat(self.op.identity, num_nodes))
	
	def root(self, x):
		parent = self.parent[x]
		if 0 <= parent:
			self.parent[x] = self.root(parent)
			self.potential[x] = self.op.operate(
				self.potential[x], self.potential[parent]
			)
			x = self.parent[x]
		return x
	
	def difference_from_root_to(self, x):
		self.root(x)
		return self.potential[x]
		
	def size(self, x):
		return -self.parent[self.root(x)]
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(
			self.difference_from_root_to(y),
			self.difference_from_root_to(x)
		)
	
	def unite(self, x, y, difference=None):
		if difference is None:
			difference = self.op.identity
		
		x, px = self.root(x), self.potential[x]
		y, py = self.root(y), self.potential[y]
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		if x == y:
			return difference == 0
		
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.potential[y] = difference
		
		return True
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)



N, M = inputs(int)
uf = UnionFind(num_nodes=N)

valid = True
for i in range(M):
	L, R, D = inputs(int)
	L -= 1
	R -= 1
	
	if not uf.unite(L, R, D):
		valid = False

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

Submission status: Accepted

Solution code:
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, input().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, *args, **kwargs):
	return np.fromiter(inputs(type, *args, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, *args, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, *args, **kwargs)
	return data

from itertools import repeat

class IntAddition (object):
	'''整数の加法'''
	def operate(self, x, y):
		return x + y
	@property
	def identity(self):
		return 0
	def cancel(self, x, y):
		return x - y
	def invert(self, x):
		return -x
	def accumulate(self, x, count):
		return x * count

class UnionFind (object):
	'''重み付きUnion-Find木'''
	def __init__(
			self,
			num_nodes=0,
			abelian_operator=IntAddition()):
		self.parent = []
		self.potential = []
		self.op = abelian_operator
		
		self.extend(num_nodes)
	
	def append(self):
		self.parent.append(-1)
		self.potential.append(self.op.identity)
	
	def extend(self, num_nodes):
		self.parent.extend(repeat(-1, num_nodes))
		self.potential.extend(repeat(self.op.identity, num_nodes))
	
	def root(self, x):
		parent = self.parent[x]
		if 0 <= parent:
			self.parent[x] = self.root(parent)
			self.potential[x] = self.op.operate(
				self.potential[x], self.potential[parent]
			)
			x = self.parent[x]
		return x
	
	def difference_from_root_to(self, x):
		self.root(x)
		return self.potential[x]
		
	def size(self, x):
		return -self.parent[self.root(x)]
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(
			self.difference_from_root_to(y),
			self.difference_from_root_to(x)
		)
	
	def unite(self, x, y, difference=None):
		if difference is None:
			difference = self.op.identity
		
		x, px = self.root(x), self.potential[x]
		y, py = self.root(y), self.potential[y]
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		if x == y:
			return difference == 0
		
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.potential[y] = difference
		
		return True
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)



N, M = inputs(int)
uf = UnionFind(num_nodes=N)

valid = True
for i in range(M):
	L, R, D = inputs(int)
	L -= 1
	R -= 1
	
	if not uf.unite(L, R, D):
		valid = False

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

Submission status: Accepted

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

class WeightedUnionFind:
  def __init__(self,n):
    self.parent = [i for i in range(n)]
    self.rank = [0] * n
    self.count = 0
    self.weight = [0] * n
  def root(self,a):
    if self.parent[a] == a:
      return a
    else:
      pa = self.root(self.parent[a])
      self.weight[a] += self.weight[self.parent[a]]
      self.parent[a] = pa
      return pa
  def is_same(self,a,b):
    return self.root(a) == self.root(b)
  def unite(self,a,b,w):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb: return
    if self.rank[ra] < self.rank[rb]:
      self.parent[ra] = rb
      self.weight[ra] = w - self.weight[a] + self.weight[b]
    else:
      self.parent[rb] = ra
      self.weight[rb] = -w - self.weight[b] + self.weight[a]
      if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
    self.count += 1
  def diff(self,a,b):
    return self.weight[a] - self.weight[b]

uf=WeightedUnionFind(n)
for l,r,d in lrd:
  l,r=l-1,r-1
  if uf.is_same(l,r):
    if uf.diff(l,r)!=d:
      print('No')
      exit(0)
  else:
      uf.unite(l,r,d)
print('Yes')

Submission status: Accepted

Solution code:

def dijkstra(node, edge, check):
    """
    nodeを含む連結グラフの中で、
    矛盾が発生しないか確認する
    矛盾が発生しない場合、
    nodeを0としたときの各ノードのスコアを返す
    """
    # 到達距離
    d = dict()
    st = [(node, 0)]
    curr_min = float('inf')
    curr_max = -float('inf')
    while st:
        curr_node, curr_d = st.pop()
        # 到達済みであれば矛盾が発生しないか確認する
        if curr_node in d.keys():
            if d[curr_node] != curr_d:
                # 矛盾が発生した
                return None, None, None, check
            else:
                continue
        # 到達した距離を記録
        d[curr_node] = curr_d 
        check[curr_node] = True
        if curr_d < curr_min:
            curr_min = curr_d
        if curr_max < curr_d:
            curr_max = curr_d

        # 隣接ノードを積む
        for nxt, diff in edge[curr_node]:
            st.append((nxt, curr_d + diff))
    
    return d, curr_min, curr_max, check


def submit():
    n, m = (int(e) for e in input().split())
    
    # グラフを構成
    edge = {i : [] for i in range(1, n + 1)}
    for _ in range(m):
        l, r, d = (int(e) for e in input().split())
        edge[l].append((r, d))
        edge[r].append((l, -d))

    check = {i: False for i in range(1, n + 1)}
    curr_max = -float('inf')

    for i in range(1, n + 1):
        if not check[i]:
            d, sub_min, sub_max, check = dijkstra(i, edge, check)

            if d == None:
                print('No')
                return
            # sub_minを0としたときのsub_maxを計算する
            sub_max -= sub_min
            if sub_max > curr_max:
                curr_max = sub_max

    if curr_max > 10 ** 9:
        print('No')
    else:
        print('Yes')


submit()

Submission status: Accepted

Solution code:
# bfs?

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    h = [0] * N  # 入り次数
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        g[L].add((R, D))
        h[R] += 1

    dist = [-1] * N

    def bfs(s):
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, d in g[v]:
                if ~dist[u]:
                    if dist[u] != dist[v] + d:
                        return False
                else:
                    dist[u] = dist[v] + d
                    dq.append(u)
        return True

    # 始点からのパスを処理
    for s in range(N):
        if h[s]: continue  # sに入ってくるパスがあるので、sを始点にしない
        # if ~dist[s]: continue
        if not bfs(s):
            print('No')
            return

    # サイクルを処理（どの点も入るパスがあり、処理できていない）
    for s in range(N):
        if ~dist[s]: continue
        if not bfs(s):
            print('No')
            return

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    h = [0] * N  # 入り次数
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        g[L].add((R, D))
        h[R] += 1

    dist = [-1] * N

    def dfs(s):
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, d in g[v]:
                if ~dist[u]:
                    if dist[u] != dist[v] + d:
                        return False
                else:
                    dist[u] = dist[v] + d
                    dq.append(u)
        return True

    # 始点からのパスを処理
    for s in range(N):
        if h[s]: continue  # sに入ってくるパスがあるので、sを始点にしない
        # if ~dist[s]: continue
        if not dfs(s):
            print('No')
            return

    # サイクルを処理（どの点も入るパスがあり、処理できていない）
    for s in range(N):
        if ~dist[s]: continue
        if not dfs(s):
            print('No')
            return

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    h = [0] * N  # 入り次数
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        g[L].add((R, D))
        h[R] += 1

    dist = [-1] * N

    def dfs(s):
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, d in g[v]:
                if ~dist[u]:
                    if dist[u] != dist[v] + d:
                        return False
                else:
                    dist[u] = dist[v] + d
                    dq.append(u)
        return True

    # 始点からのパスを処理
    for s in range(N):
        if h[s]: continue  # sに入ってくるパスがあるので、sを始点にしない
        if ~dist[s]: continue
        if not dfs(s):
            print('No')
            return

    # サイクルを処理（どの点も入るパスがあり、処理できていない）
    for s in range(N):
        if ~dist[s]: continue
        if not dfs(s):
            print('No')
            return

    print('Yes')


if __name__ == '__main__':
    main()

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)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[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)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


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

wuf = WeightedUnionFind(n)

for item in lrd:
    if wuf.same(item[0], item[1]):
        if wuf.diff(item[0], item[1]) != item[2]:
            print('No')
            exit()
    else:
        wuf.union(item[0], item[1], item[2])

print('Yes')

Submission status: Accepted

Solution code:
visited=set()
success=1
import sys
sys.setrecursionlimit(1000000)
def dfs(graph, node):
  global visited
  global b
  global success
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          success=0
      dfs(graph, graph[node-1][0][counter])
      
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  if i+1 in visited:
    continue
  b[i]=0
  dfs(a,i+1)
if success==0:
  print('No')
else:
  print('Yes')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        L, R, D = map(int, input().split())
        tree[L - 1].append((R - 1, D))
        tree[R - 1].append((L - 1, -D))

    def dfs(v):
        for u, d in tree[v]:
            if depth[u] == f_inf:
                depth[u] = depth[v] + d
                dfs(u)
            else:
                if depth[u] != depth[v] + d:
                    print("No")
                    exit()

    depth = [f_inf for _ in range(n)]
    for i in range(n):
        if depth[i] == f_inf:
            depth[i] = 0
            dfs(i)

    print("Yes")


if __name__ == '__main__':
    resolve()