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:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

class UnionFind_weight:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n
        # 親との差分
        self.weight = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            p = self.par[x]  # 根につなぎ直す前の親をメモ
            self.par[x] = self.find(self.par[x])
            self.weight[x] += self.weight[p]
            return self.par[x]

    # 併合
    # x → y の重みを w とする。
    def unite(self, x, y, w):
        w += self.weight[x] - self.weight[y]
        x = self.find(x)
        y = self.find(y)
        if x != y:  # 異なる集合に属する場合のみ併合
            if self.rank[x] < self.rank[y]:  # 高い方をxとする。
                x,y = y,x
                w = -w
            if self.rank[x] == self.rank[y]:  # 同じ高さの時は高さ+1
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える。重みも更新。
            self.par[x] += self.par[y]
            self.par[y] = x
            self.weight[y] = w

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]
    
    # x → y の重み
    def diff(self, x, y):
        return self.weight[y] - self.weight[x]

n,m = readints()

u = UnionFind_weight(n)

ans = 1
for i in range(m):
    l,r,d = readints()
    l-=1;r-=1
    if u.same(l,r):
        if u.diff(l,r) != d:
            ans = 0
            break
    else:
        u.unite(l,r,d)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

for _ in [0]*M:
  a, b, d = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append((b, d))
  G[b].append((a, -d))

X = [None]*N

def dfs(i, x=0):
  for j, d in G[i]:
    if X[j] is None:
      X[j] = x+d
      dfs(j, x+d)
    elif X[j] != x+d:
      print('No')
      exit()

for i in range(N):
  if X[i] is not None:
    continue
  X[i] = 0
  dfs(i)
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque 
#スタック
s = deque([])

N,M=map(int,input().split())
G = [[] for i in range(N+1)]

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

ans = True
X = [None]*(N+1)
for i in range(1,N+1):

    if X[i]==None:
        s.append([i,0])

    while len(s)>0:#dfs
        j,x = s.pop()
        if X[j]==None:
            X[j]=x
            for nex in G[j]:
                s.append([nex[0],x+nex[1]])
        else:
            if X[j]!=x:
                ans = False
                break

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

Submission status: Accepted

Solution code:
from collections import deque
def check():
  N, M = map(int, input().split())
  edge = [[] for _ in range(N)]
  for i in range(M):
    a,b,d = map(int, input().split())
    edge[a-1].append([b-1,d])
    edge[b-1].append([a-1,-d])
  
  visited = [float('inf')]*N
  D = deque()
  for i in range(N):
    if visited[i]==float('inf'):
      visited[i]=0
      D.append(i)
      while len(D)>0:
        v = D.popleft()
        for w,d in edge[v]:
          if visited[w]==float('inf'):
            visited[w] = visited[v]+d
            D.append(w)
          elif visited[w]!=visited[v]+d:
            return 'No'
  return 'Yes'
print(check())

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

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


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    uf = UnionFind(N+1)
    try:
        for l, r, d in zip(L, R, D):
            uf.merge(l, r, d)
        return YES
    except MergeError:
        return NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    D = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        D[i] = int(next(tokens))
    print(solve(N, M, L, R, D))
    
class MergeError(Exception):
    pass

# 参考: https://qiita.com/drken/items/cce6fc5c579051e64fab
class UnionFind:
    def __init__(self, size: int):
        self.par = list(range(size))
        self.rank = [0] * size
        self.diff_weight = [0] * size

    def root(self, x: int):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.diff_weight[x] += self.diff_weight[self.par[x]] # 累積和をとる        
        #return par[x] := r
        self.par[x] = r
        return r

    def weight(self, x: int):
        self.root(x) # 経路圧縮
        return self.diff_weight[x]

    def same(self, x: int, y: int):
        return self.root(x) == self.root(y)

    # weight(y) - weight(x) = w となるように merge する
    def merge(self, x: int, y: int, w: int):
        # x と y それぞれについて、 root との重み差分を補正
        adjusted_w = w + self.weight(x) - self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            if adjusted_w != 0:
                raise MergeError
            return
        if self.rank[x] < self.rank[y]:
            x, y, adjusted_w = y, x, -adjusted_w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.diff_weight[y] = adjusted_w

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
dist = [[] for i in range(N)]
for i in range(M):
    l, r, d = getNM()
    dist[l - 1].append([r - 1, d])
    dist[r - 1].append([l - 1, -d])

dis = [float('inf')] * N

pos = deque([i for i in range(N)])
while len(pos) > 0:
    u = pos.popleft()
    # 始めの第一歩
    if dis[u] == float('inf'):
        dis[u] = 0
    # 行き先の位置が未確定なら確定させる
    # 既に確定しているなら判定
    for to, d in dist[u]:
        if dis[to] == float('inf'):
            dis[to] = dis[u] + d
            # 位置をレコードした頂点を優先的に処理する必要があるためappendleft
            # 例 que = [0, 2, 1], [1, 2, 3]
            # pos = [0, 1, 2] の時
            # dis = [0, -2, 1]でYesになるはず
            # 0を探索, 1の距離をレコードしてappend disは[0, inf, 1]
            # pos = [1, 2, 2]のため次は1を探索
            # dis[1] == infなのでdis[1] = 0にする
            # dis[1] = 0, dis[2] = 1なのでNo
            pos.appendleft(to)
        else:
            if dis[u] + d != dis[to]:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, M = getNM()
dist = [[] for i in range(N)]
for i in range(M):
    l, r, d = getNM()
    dist[l - 1].append([r - 1, d])
    dist[r - 1].append([l - 1, -d])

dis = [float('inf')] * N

pos = deque([i for i in range(N)])
while len(pos) > 0:
    u = pos.popleft()
    # 始めの第一歩
    if dis[u] == float('inf'):
        dis[u] = 0
    # 行き先の位置が未確定なら確定させる
    # 既に確定しているなら判定
    for to, d in dist[u]:
        if dis[to] == float('inf'):
            dis[to] = dis[u] + d
            pos.appendleft(to)
        else:
            if dis[u] + d != dis[to]:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
g=[[] for _ in range(n+1)]
visited=[0]*(n+1)
x=[0]*(n+1)

for _ in range(m):
    l,r,d=list(map(int,input().split()))

    g[r].append((l,d))
    g[l].append((r,-d))

stack=list(range(1,n+1))

while len(stack)>0:
    u=stack.pop()

    visited[u]=1

    for v,d in g[u]:
        if visited[v]==1:
            continue

        x[v]=x[u]-d

        stack.append(v)

flag=True

for i in range(1,n+1):
    for j,d in g[i]:
        if x[i]-x[j]!=d:
            flag=False

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    graph[l-1].append((r-1, d))
    graph[r-1].append((l-1, -d))
seen = [False]*n
dist = [None]*n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    dist[i] = 0
    while q:
        node = q.popleft()
        if seen[node]:
            continue
        seen[node] = True
        for c_node, d in graph[node]:
            if dist[c_node] is None:
                dist[c_node] = dist[node] + d
            elif dist[c_node] != dist[node] + d:
                print('No')
                exit(0)
            q.append(c_node)
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    graph[l-1].append((r-1, d))
    graph[r-1].append((l-1, -d))
seen = [False]*n
dist = [None]*n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    dist[i] = 0
    while q:
        node = q.popleft()
        if seen[node]:
            continue
        seen[node] = True
        for c_node, d in graph[node]:
            if dist[c_node] is None:
                dist[c_node] = dist[node] + d
            elif dist[c_node] != dist[node] + d:
                print('No')
                exit(0)
            if not seen[c_node]:
                q.append(c_node)
print('Yes')

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


class WeightedUnionFind():
    """
    https://qiita.com/drken/items/cce6fc5c579051e64fab
    UnionFindTreeに親ノードへ向かう辺の重みを追加したもの。
    これによりノードx, yがpath-connectedな場合にその間の符号付き距離をO(logN)で取得できる。
    ただしこれは「有向辺」であることに注意。
    というのも距離の導出は各ノードから根ノードまでの距離を取ってその差分で求めているため、
    無向辺の場合はLCAを求めないといけない。そしてUnionFindでは経路圧縮のせいでLCAを求めるのは不可能。
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する。
        parentsは各ノードの属する木の根を表す。
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する。
        diff_weightは各ノードから親ノードへ向かう辺の重みを格納する。
        根ノードに格納する重みは0とする。
        """
        self.n = n
        self.parents = [-1] * n
        self.diff_weight = [0] * n

    def find(self, x):
        """
        xの属する木の根を返す。
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す。
        """
        if self.parents[x] < 0:
            return x
        else:
            edge_weight = self.diff_weight[x]
            prev_parent = self.parents[x]
            self.parents[x] = self.find(self.parents[x])
            self.diff_weight[x] = self.diff_weight[prev_parent] + edge_weight
            return self.parents[x]

    def union(self, x, y, w):
        """
        xからyへ重みwの辺を繋ぐ。
        既にx, yがpath-connectedな場合はFalseを返す。
        そうでなければTrueを返す。
        """
        rx = self.find(x)
        ry = self.find(y)
        w += self.diff_weight[y] - self.diff_weight[x]
        w *= -1 # 内部処理的にはfind(y) -> find(x)へ辺を繋ぐ

        if rx == ry:
            return False

        if self.parents[rx] > self.parents[ry]:
            rx, ry = ry, rx # xの方が木のサイズが大きいようにする
            w *= -1 # それに応じて結ぶ辺の向きも反転させる

        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        self.diff_weight[ry] = w
        return True

    def weight(self, x):
        """
        xからxの属する木の根ノードまでの重みを求める
        """
        _ = self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        """
        xからyへ向かうのにかかる重みを求める
        """
        return self.weight(x) - self.weight(y)

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, input().split())
    tree = WeightedUnionFind(N)
    for _ in range(M):
        l, r, d = map(int, input().split())
        l, r = l-1, r-1
        if tree.same(l, r):
            dist = tree.diff(l, r)
            if d != dist:
                print("No")
                return
        else:
            tree.union(l, r, d)
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
q = deque([])
visited = set()
dist = [None] * (n + 1)

for i in range(m):
    a, b, k = map(int, input().split())
    g[a].append((b, k))
    g[b].append((a, -k))

def dfs(u):
    q.append(u)
    while q:
        v = q.pop()
        visited.add(v)
        for x, d in g[v]:
            if x not in visited:
                if dist[x] is None:
                    dist[x] = dist[v] + d
                elif dist[x] != dist[v] + d:
                    return False
                q.append(x)
    return True

for i in range(1, n + 1):
    if i not in visited:
        dist[i] = 1
        if not dfs(i):
            print("No")
            exit()
print("Yes")

Submission status: Accepted

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

G = [[] for _ in range(n)]
dist = dict()
for l, r, d in LRD:
    l -= 1
    r -= 1
    G[l].append(r)
    G[r].append(l)
    dist[(l, r)] = d
    dist[(r, l)] = -d

INF = 10**18
X = [INF] * n
for i in range(n):
    stack = [i]
    while stack:
        u = stack.pop()
        if X[u] == INF:
            X[u] = 0
        for v in G[u]:  # u -> v
            if X[v] == INF:
                X[v] = X[u] + dist[(u, v)]
                stack.append(v)
            else:
                if X[v] != X[u] + dist[(u, v)]:
                    print("No")
                    exit()

print("Yes")

Submission status: Accepted

Solution code:
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    q = deque([])
    visited = set()
    inf = 10 ** 10
    dist = [-inf] * (n + 1)

    for i in range(m):
        a, b, k = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k


    def dfs(u):
        q.append(u)
        while q:
            v = q.pop()
            visited.add(v)
            for x in g[v]:
                if x not in visited:
                    if ref[(v, x)] != []:
                        y = ref.get((v, x))
                        if dist[x] == -inf:
                            dist[x] = dist[v] + y
                        elif dist[x] != dist[v] + y:
                            print("No")
                            exit()
                    else:
                        y = ref.get((x, v))
                        if dist[x] == -inf:
                            dist[x] = dist[v] - y
                        elif dist[v] != dist[x] + y:
                            print("No")
                            exit()
                    q.append(x)


    for i in range(1, n + 1):
        if i not in visited:
            dist[i] = 1
            dfs(i)
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    q = deque([])
    visited = set()
    inf = 10 ** 10
    dist = [-inf] * (n + 1)

    for i in range(m):
        a, b, k = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k


    def dfs(u):
        q.append(u)
        while q:
            v = q.pop()
            visited.add(v)
            for x in g[v]:
                if x not in visited:
                    if ref[(v, x)] != []:
                        y = ref.get((v, x))
                        if dist[x] == -inf and dist[v] == -inf:
                            continue
                        elif dist[x] == -inf:
                            dist[x] = dist[v] + y
                        elif dist[v] == -inf:
                            dist[v] = dist[x] - y
                        elif dist[x] != dist[v] + y:
                            #print(v, x, dist[v], dist[x], y)
                            print("No")
                            exit()
                    else:
                        y = ref.get((x, v))
                        if dist[x] == -inf and dist[v] == -inf:
                            continue
                        elif dist[v] == -inf:
                            dist[v] = dist[x] + y
                        elif dist[x] == -inf:
                            dist[x] = dist[v] - y
                        elif dist[v] != dist[x] + y:
                            #print(v, x, dist[v], dist[x], y)
                            print("No")
                            exit()
                    q.append(x)


    for i in range(1, n + 1):
        if i not in visited:
            #print(len(visited))
            dist[i] = 1
            dfs(i)
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  tree = [[] for _ in range(n)]
  for i in range(m):
    l, r, d = map(int, input().split())
    tree[l-1].append((r-1, d))
    tree[r-1].append((l-1, -d))
  
  ans = [0]*n
  not_yet = deque([])
  already = [False]*n
  judge = True
  
  for i in range(n):
    if already[i]:
      continue
    already[i] = True
    for v in tree[i]:
      index, dist = v[0], v[1]
      ans[index] = dist
      already[index] = True
      not_yet.append(index)
    while not_yet:
      index = not_yet.popleft()
      for v in tree[index]:
        index2, dist = v[0], v[1]
        if already[index2]:
          if ans[index] + dist != ans[index2]:
            judge = False
        else:
          already[index2] = True
          ans[index2] = ans[index] + dist
          not_yet.append(index2)
          
  print("Yes" if judge else "No")
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**9
eps = 10**-7

N,M = map(int,input().split())
# 1-indexed union-find
# parent(親)
par = [i for i in range(N+1)]
# rank(深さ)
rank = [0]*(N+1)
# 同グループの頂点数
# size = [1]*(N+1)

# 木の根を求める
def root(x):
    if par[x] == x:             # 根の時
        return x
    else:
        par[x] = root(par[x])   # 経路圧縮
        return par[x]

# xとyの属する集合を併合(ランク有)
def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              # xの親をyに
        #size[y] += size[x]      # yの頂点数+=xの頂点数
    else:
        par[y] = x              # yの親をxに
        #size[x] += size[y]      # xの頂点数+=yの頂点数
        if rank[x] == rank[y]:
            rank[x] += 1

LRD = [tuple(map(int,readline().split())) for i in range(M)]

for (L,R,D) in LRD:
    unite(L,R)

from collections import defaultdict,deque
rel = defaultdict(lambda: [])

for (L,R,D) in LRD:
    rel[root(L)].append((L,R,D))

for k,v in rel.items():
    dist = defaultdict(lambda: [])
    for (L,R,D) in v:
        dist[L].append((R,D))
        dist[R].append((L,-D))
    que = deque([])
    x = {}
    for k1,v1 in dist.items():
        x[k1] = 0
        for (to,dis) in v1:
            x[to] = dis
            que.append(to)
        break
    while que:
        fro = que.popleft()
        for (to,dis) in dist[fro]:
            if to not in x.keys():
                x[to] = x[fro] + dis
                que.append(to)
    for (L,R,D) in v:
        if x[R] - x[L] != D:
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**9
eps = 10**-7

N,M = map(int,input().split())
# 1-indexed union-find
# parent(親)
par = [i for i in range(N+1)]
# rank(深さ)
rank = [0]*(N+1)
# 同グループの頂点数
# size = [1]*(N+1)

# 木の根を求める
def root(x):
    if par[x] == x:             # 根の時
        return x
    else:
        par[x] = root(par[x])   # 経路圧縮
        return par[x]

# xとyの属する集合を併合(ランク有)
def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              # xの親をyに
        #size[y] += size[x]      # yの頂点数+=xの頂点数
    else:
        par[y] = x              # yの親をxに
        #size[x] += size[y]      # xの頂点数+=yの頂点数
        if rank[x] == rank[y]:
            rank[x] += 1

LRD = [tuple(map(int,readline().split())) for i in range(M)]

for (L,R,D) in LRD:
    unite(L,R)

from collections import defaultdict,deque
rel = defaultdict(lambda: [])

for (L,R,D) in LRD:
    rel[root(L)].append((L,R,D))

for k,v in rel.items():
    dist = defaultdict(lambda: [])
    for (L,R,D) in v:
        dist[L].append((R,D))
        dist[R].append((L,-D))
    que = deque([])
    x = {}
    for k1,v1 in dist.items():
        x[k1] = 0
        for (to,dis) in v1:
            x[to] = dis
            que.append(to)
        break
    while que:
        fro = que.popleft()
        for (to,dis) in dist[fro]:
            if to not in x.keys():
                x[to] = x[fro] + dis
                que.append(to)
    for (L,R,D) in v:
        if x[R] - x[L] != D:
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**9
eps = 10**-7

N,M = map(int,input().split())
# 1-indexed union-find
# parent(親)
par = [i for i in range(N+1)]
# rank(深さ)
rank = [0]*(N+1)
# 同グループの頂点数
# size = [1]*(N+1)

# 木の根を求める
def root(x):
    if par[x] == x:             # 根の時
        return x
    else:
        par[x] = root(par[x])   # 経路圧縮
        return par[x]

# xとyの属する集合を併合(ランク有)
def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              # xの親をyに
        #size[y] += size[x]      # yの頂点数+=xの頂点数
    else:
        par[y] = x              # yの親をxに
        #size[x] += size[y]      # xの頂点数+=yの頂点数
        if rank[x] == rank[y]:
            rank[x] += 1

LRD = [tuple(map(int,readline().split())) for i in range(M)]

for (L,R,D) in LRD:
    unite(L,R)

from collections import defaultdict,deque
rel = defaultdict(lambda: [])

for (L,R,D) in LRD:
    rel[root(L)].append((L,R,D))

for k,v in rel.items():
    dist = defaultdict(lambda: [])
    for (L,R,D) in v:
        dist[L].append((R,D))
        dist[R].append((L,-D))
    que = deque([])
    x = {}
    for k1,v1 in dist.items():
        x[k1] = 0
        for (to,dis) in v1:
            x[to] = dis
            que.append(to)
        break
    while que:
        fro = que.popleft()
        for (to,dis) in dist[fro]:
            if to not in x.keys():
                x[to] = x[fro] + dis
                que.append(to)
    for (L,R,D) in v:
        if x[R] - x[L] != D:
            print('No')
            exit()
    if max(x.values()) - min(x.values()) > 10**9:
        print('No')
        exit()
print('Yes')