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:
from collections import deque

n, m = 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])

x = [None for i in range(n)]

def f():
    for i in range(n):
        if x[i] == None:
            x[i] = 0
            q = deque([i])
            while len(q):
                j = q.popleft()
                for k, d in graph[j]:
                    if x[k] == None:
                        q.append(k)
                        x[k] = x[j] + d
                    elif x[k] != x[j] + d:
                        return False
    return True

if f():
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
n,m=I()
r=range(n)
y=[[] for i in r]
z=[None for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i-1]+=[[j-1, k]]
  y[j-1]+=[[i-1,-k]]

for i in r:
  if z[i]==None:
    z[i]=0 
  q=[i]
  while q:
    p=q.pop()
    for j,k in y[p]:
      if z[j]==None:
        q+=[j]
        z[j]=z[p]+k
      elif z[j]!=z[p]+k:
        print("No")
        exit()
print("Yes")

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def main():
    N, M = map(int, input().split())
    m = defaultdict(list)
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        m[L].append((R, D))
        m[R].append((L, -D))

    x = [None] * N
    for k in range(N):
        if x[k] is not None:
            continue

        x[k] = 0
        que = deque()
        que.append(k)
        while len(que) != 0:
            i = que.popleft()

            for j, d in m[i]:
                if x[j] is None:
                    x[j] = x[i] + d
                    que.append(j)
                else:
                    if x[j] != x[i] + d:
                        print(No)
                        return

    print(Yes)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class WeightedUnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        self.diff_weight = [0 for i in range(self.n)]
        
    # ノードxのルートを求める
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            r = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return self.par[x]
        
    # ノードxのルートからの距離を求める
    def weight(self, x:int) -> int:
        self.find(x)
        return self.diff_weight[x]
        
    # weight(y) - weight(x) = w となるようにする
    def unite(self, x:int, y:int, w:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        w += self.weight(x)
        w -= self.weight(y)
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            w = -w

        self.par[ry] = self.par[rx]
        self.diff_weight[ry] = w
        
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    def diff(self, x:int, y:int) -> int:
        if self.isSame(x,y):
            return self.weight(y)-self.weight(x)
        else:
            raise ValueError("xとyは同じ木に属していません")


  
N,M = map(int, input().split())
query = []
for _ in range(M):
    query.append(tuple(map(int, input().split())))
    
uf = WeightedUnionFind(N)
    
consistent = True
for l,r,d in query:
    l -= 1
    r -= 1
    if uf.isSame(l,r):
        if d != uf.diff(l,r):
            consistent = False
            break
    else:
        uf.unite(l,r,d)
        
if consistent:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        self.diff_weight = [0 for i in range(self.n)]
        
    # ノードxのルートを求める
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            r = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return self.par[x]
        
    # ノードxのルートからの距離を求める
    def weight(self, x:int) -> int:
        self.find(x)
        return self.diff_weight[x]
        
    # weight(y) - weight(x) = w となるようにする
    def unite(self, x:int, y:int, w:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        w += self.weight(x)
        w -= self.weight(y)
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            w = -w

        self.par[ry] = self.par[rx]
        self.diff_weight[ry] = w
        
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    def diff(self, x:int, y:int) -> int:
        if self.isSame(x,y):
            return self.weight(y)-self.weight(x)
        else:
            raise ValueError("xとyは同じ木に属していません")


  
N,M = map(int, input().split())
query = []
for _ in range(M):
    query.append(tuple(map(int, input().split())))
    
uf = WeightedUnionFind(N)
    
consistent = True
for l,r,d in query:
    l -= 1
    r -= 1
    if uf.isSame(l,r):
        if d != uf.diff(l,r):
            consistent = False
            break
    else:
        uf.unite(l,r,d)
        
if consistent:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
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(( d,r - 1))
    graph[r - 1].append((-d,l - 1))

INF = float("inf")
dist = [-INF]*n

# 未探索ノードの距離を0とする
for n in range(n):
    if dist[n] != -INF:
        continue
    else:
        stack = [n]
        dist[n] = 0
        
    # stackが空になるまで探索を繰り返す
    while len(stack):
        cur = stack.pop()
        
        # ノードcurと隣り合う未探索ノードをstackに追加
        for cost, nex_node in graph[cur]:
            if dist[nex_node] != -INF:
                continue
            else:
                dist[nex_node] = dist[cur] + cost
                stack.append(nex_node)

def solve():
    for i in range(n):
        for d,node in graph[i]:
            if dist[node]-dist[i] != d:
                print("No")
                return 0
            
    print("Yes")
    return 0

solve()

Submission status: Accepted

Solution code:
from collections import deque

class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph


class DfsAndBfs:
 
  # グラフは隣接リスト 0-originであることに注意
  # graph[i]はi番目のノードと隣り合うノードの(距離, ノード番号)を格納している
  # 例：0番と3番の距離が7 -> graph[0] = [[(7,3)]] 
  @classmethod
  def dfs(cls, graph:list, node:int) -> list:
    # 未探索のノードは距離を-1とする
    INF = float("inf")
    dist = [-INF]*node  
    
    # 未探索ノードの距離を0とする
    for n in range(node):
        if dist[n] != -INF:
            continue
        else:
            stack = [n]
            dist[n] = 0
            
        # stackが空になるまで探索を繰り返す
        while len(stack):
            cur = stack.pop()
            
            # ノードcurと隣り合う未探索ノードをstackに追加
            for cost, nex_node in graph[cur]:
                if dist[nex_node] != -INF:
                    continue
                else:
                    dist[nex_node] = dist[cur] + cost
                    stack.append(nex_node)

    return dist
 
  
  # グラフは隣接リスト 0-originであることに注意
  # graph[i]はi番目のノードと隣り合うノードの(距離, ノード番号)を格納している
  # 例：0番と3番の距離が7 -> graph[0] = [[(7,3)]]
  @classmethod
  def bfs(cls, graph:list, node:int) -> list:
      # 未探索のノードは距離を-1とする
      INF = float("inf")
      dist = [-INF]*node

      # 未探索ノードの距離を0とする
      for n in range(node):
          if dist[n] != -INF:
              continue
          else:
              que = deque([n])
              dist[n] = 0

          # queが空になるまで探索を繰り返す
          while len(que):
              cur = deque.popleft(que)

              # ノードcurと隣り合う未探索ノードをqueに追加
              for cost, nex_node in graph[cur]:
                  if dist[nex_node] != -INF:
                      continue
                  else:
                      dist[nex_node] = dist[cur] + cost
                      que.append(nex_node)

      return dist
  

N,M = map(int ,input().split())
LRD = []
for i in range(M):
    LRD.append(tuple(map(int ,input().split())))

graphMaker = MakeGraph(N, False)
add_edge = graphMaker.add_drct_edge_lst
for l,r,d in LRD:
    add_edge(l-1,r-1,d)
    add_edge(r-1,l-1,-d)
    
graph = graphMaker.get_graph()

dist = DfsAndBfs.bfs(graph, N)



consistent = True

for l,r,d in LRD:
    if dist[r-1] - dist[l-1] == d:
        continue
    else:
        consistent = False
        break

    
if consistent:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque

class MakeGraph:
    
    # 隣接行列もしくは隣接リストの初期化
    # node_num：ノード数
    # isMat：隣接行列(True) / 隣接リスト(False)
    def __init__(self, node_num:int, isMat:bool) -> None:
        self.n = node_num
        self.isMat = isMat

        # 隣接行列の初期化
        if self.isMat:
            INF = float("inf")
            self.graph = [[INF for _ in range(self.n)] for _ in range(self.n)]
    
        # 隣接リストの初期化
        else:
            self.graph = [[] for _ in range(self.n)]

    # エッジの追加
    # frm, to：起点ノード, 終点ノード
    # dist：frm→toへのコスト
    def add_undr_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        self.graph[to][frm] = dist
        
    def add_drct_edge_mat(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm][to] = dist
        
    def add_undr_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))
        self.graph[to].append((dist, frm))
        
    def add_drct_edge_lst(self, frm:int, to:int, dist:int) -> None:
        self.graph[frm].append((dist, to))

                
    # 完成したグラフを取り出す
    def get_graph(self) -> list:
        return self.graph


class DfsAndBfs:
 
  # グラフは隣接リスト 0-originであることに注意
  # graph[i]はi番目のノードと隣り合うノードの(距離, ノード番号)を格納している
  # 例：0番と3番の距離が7 -> graph[0] = [[(7,3)]] 
  @classmethod
  def dfs(cls, graph:list, node:int) -> list:
    # 未探索のノードは距離を-1とする
    INF = float("inf")
    dist = [-INF]*node  
    
    # 未探索ノードの距離を0とする
    for n in range(node):
        if dist[n] != -INF:
            continue
        else:
            stack = [n]
            dist[n] = 0
            
        # stackが空になるまで探索を繰り返す
        while len(stack):
            cur = stack.pop()
            
            # ノードcurと隣り合う未探索ノードをstackに追加
            for cost, nex_node in graph[cur]:
                if dist[nex_node] != -INF:
                    continue
                else:
                    dist[nex_node] = dist[cur] + cost
                    stack.append(nex_node)

    return dist
 
  
  # グラフは隣接リスト 0-originであることに注意
  # graph[i]はi番目のノードと隣り合うノードの(距離, ノード番号)を格納している
  # 例：0番と3番の距離が7 -> graph[0] = [[(7,3)]]
  @classmethod
  def bfs(cls, graph:list, node:int) -> list:
      # 未探索のノードは距離を-1とする
      INF = float("inf")
      dist = [-INF]*node

      # 未探索ノードの距離を0とする
      for n in range(node):
          if dist[n] != -INF:
              continue
          else:
              que = deque([n])
              dist[n] = 0

          # queが空になるまで探索を繰り返す
          while len(que):
              cur = deque.popleft(que)

              # ノードcurと隣り合う未探索ノードをqueに追加
              for cost, nex_node in graph[cur]:
                  if dist[nex_node] != -INF:
                      continue
                  else:
                      dist[nex_node] = dist[cur] + cost
                      que.append(nex_node)

      return dist
  

N,M = map(int ,input().split())
LRD = []
for i in range(M):
    LRD.append(tuple(map(int ,input().split())))

graphMaker = MakeGraph(N, False)
add_edge = graphMaker.add_drct_edge_lst
for l,r,d in LRD:
    add_edge(l-1,r-1,d)
    add_edge(r-1,l-1,-d)
    
graph = graphMaker.get_graph()

dist = DfsAndBfs.dfs(graph, N)



consistent = True

for l,r,d in LRD:
    if dist[r-1] - dist[l-1] == d:
        continue
    else:
        consistent = False
        break

    
if consistent:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["nodes", "weight"]
    
    def __init__(self, n: int) -> None:
        self.nodes = [-1]*n
        self.weight = [0]*n
        
    def get_root(self, x:int) -> int:
        if x<0:
            raise ValueError("Negative Index")
        
        if self.nodes[x]<0:
            return x
        else:
            parent, self.nodes[x] = self.nodes[x], self.get_root(self.nodes[x])
            self.weight[x] += self.weight[parent]
            return self.nodes[x]

    def unite(self, x:int, y:int) -> None:
        if x<0 or y<0:
            raise ValueError("Negative Index")
            
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            if self.nodes[root_x] < self.nodes[root_y]:
                bigroot, smallroot = root_x, root_y
            else:
                bigroot, smallroot = root_y, root_x
                
            self.nodes[bigroot] += self.nodes[smallroot]
            self.nodes[smallroot] = bigroot

    def relate(self, smaller:int, bigger:int, diff_weight:int) -> None:
        if smaller<0 or bigger<0:
            raise ValueError("Negative Index")
            
        s_root, b_root = self.get_root(smaller), self.get_root(bigger)
        if s_root == b_root:
            if self.weight[smaller] + diff_weight == self.weight[bigger]:
                return
            raise ValueError
            
        else:
            self.weight[b_root] = diff_weight - self.weight[bigger]
            self.nodes[s_root] += self.nodes[b_root]
            self.nodes[b_root] = smaller
            
   
         
N,M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))
 
uf = UnionFind(N)
relate = uf.relate    

try:
    for l,r,d in LRD:
        relate(l-1,r-1,d)
    print("Yes")
except Exception as e:
    print("No")

Submission status: Accepted

Solution code:
class WeightedUnionFind:
    """
    重み付きUnionFind

    """
    root_position = 0

    def __init__(self, size: int):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.parent = [-1] * size
        self.weight = [WeightedUnionFind.root_position] * size

    def find(self, x: int) -> (int, int):
        """
        xを含む集合の代表とxの代表からの位置を求める
        """
        if self.parent[x] < 0:
            return x, self.weight[x]
        root, weight = self.find(self.parent[x])
        self.parent[x] = root
        self.weight[x] += weight
        return root, self.weight[x]

    def union(self, x: int, y: int, weight: int) -> bool:
        """
        xを含む集合とyを含む集合を併合する
        `weight[x] + weight = weight[y]`になるように辺に重みをもたせる。
        xとyがすでに同じ集合に含まれている場合Falseを返す。
        """
        root_x, weight_x = self.find(x)
        root_y, weight_y = self.find(y)

        if root_x == root_y:
            return False

        if self.parent[root_x] >= self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
            self.weight[root_y] = weight_x + weight - weight_y
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
            self.weight[root_x] = weight_y - weight - weight_x

        return True


def main():
    n, m = map(int, input().split())
    wut = WeightedUnionFind(n)
    for _ in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        merged = wut.union(l, r, d)
        if not merged:
            root_l, weight_l = wut.find(l)
            root_r, weight_r = wut.find(r)
            if root_l != root_r or weight_l + d != weight_r:
                return False
    return True


if __name__ == '__main__':
    result = main()
    print('Yes' if result else 'No')

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 root(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.root(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.root(x)
        ry = self.root(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.root(x) == self.root(y)

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

N,M = map(int,input().split())
wuf = WeightedUnionFind(N)
for i in range(M):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    if (wuf.same(l,r)):
        diff = wuf.diff(l,r)
        if (diff != d):
            print("No")
            quit()
    else:
        wuf.union(l,r,d)
print("Yes")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, LRD):
    # print(LRD)
    g = [[] for _ in range(N)]
    ns = set([])
    for l ,r, d in LRD:
        g[l-1].append((r-1,d))
        g[r-1].append((l-1,-d))
        ns.add(l-1)
        ns.add(r-1)      
    
    G =  [None for _ in range(N)]

    if M == 0:
        return 'Yes'

    ns = {n:n for n in ns}
    while ns:
        # q = [list(ns.keys())[0]]
        for k in ns.keys():
            q = [k]
            break
        ns.pop(q[0])
        # print(q)
        G[q[0]] = 0
        while q:
            n = q.pop()
            for r, d in g[n]:
                if G[r] is None:
                    G[r] = G[n] + d
                    q.append(r)
                    # if r in ns:
                    ns.pop(r)
                else:
                    if G[r] != G[n] + d:
                        return 'No'
                        # pass
    
    return 'Yes'
            



def main():
    N, M = read_int_n()
    LRD = [read_int_n() for _ in range(M)]

    # N = 100000
    # M = 200000
    # LRD = [[random.randint(1, N), random.randint(1, N), random.randint(1, 10000)] for _ in range(M) ]
    print(slv(N, M, LRD))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def search(i, total):
  for dist, to in edges[i]:
    if dists[to] == None:
      dists[to] = total + dist
      if not search(to, total + dist):
        return False
    else:
      if dists[to] == total + dist:
        continue
      else:
        return False
  return True

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

dists = [None] * n

for i in range(n):
  if dists[i] == None:
    dists[i] = 0
    if not search(i, 0):
      print("No")
      break
else:
  print("Yes")

Submission status: Accepted

Solution code:
import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L-=1
    R-=1
    G[L][R]=D
    G[R][L]=-D
P=[0 for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
for i in range(N):
    if reached[i]==0:
        q.put(i)
        reached[i]=1
        while(not(q.empty())):
            p=q.get()
            for r in G[p]:
                if reached[r]==0:
                    q.put(r)
                    P[r]=P[p]+G[p][r]
                else:
                    if P[r]!=P[p]+G[p][r]:
                        print("No")
                        exit()
                reached[r]=1
print("Yes")

Submission status: Accepted

Solution code:
class weight_union_find(object):
    def __init__(self, n):
        self.par = [-1 for i in range(n)]
        self.weight_diff = [0 for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def root(self, ind):
        if self.par[ind] < 0:
            return ind
        else:
            r = self.root(self.par[ind])
            self.weight_diff[ind] += self.weight_diff[self.par[ind]]
            self.par[ind] = r
            return r

    def unite(self, ind1, ind2, w):
        root1 = self.root(ind1)
        root2 = self.root(ind2)
        if root1 == root2:
            # 重みが違う==解無し
            # print(root1, root2, self.weight_diff[ind1], self.weight_diff[ind2], w)
            if -(self.weight_diff[ind1] - self.weight_diff[ind2]) == w:
                return True
            else:
                return False
        else:
            #swap
            if self.rank[root1] == self.rank[root2]:
                self.rank[root1] += 1
            if self.rank[root1] < self.rank[root2]:
                root1, root2 = root2, root1
                ind1, ind2 = ind2, ind1
                w *= -1
            self.par[root1] += self.par[root2]
            self.par[root2] = root1
            self.weight_diff[root2] = w + self.weight_diff[ind1] - self.weight_diff[ind2]
            return True



n, m = list(map(int, input().split()))
query = []
for i in range(m):
    query.append(list(map(int, input().split())))
uf = weight_union_find(n)
for l, r, d in query:
    if not uf.unite(l-1, r-1, d):
        print("No")
        exit()
print("Yes")

Submission status: Accepted

Solution code:
class weight_union_find(object):
    def __init__(self, n):
        self.par = [-1 for i in range(n)]
        self.weight_diff = [0 for i in range(n)]
    
    def root(self, ind):
        if self.par[ind] < 0:
            return ind
        else:
            r = self.root(self.par[ind])
            self.weight_diff[ind] += self.weight_diff[self.par[ind]]
            self.par[ind] = r
            return r

    def unite(self, ind1, ind2, w):
        root1 = self.root(ind1)
        root2 = self.root(ind2)
        if root1 == root2:
            # 重みが違う==解無し
            # print(root1, root2, self.weight_diff[ind1], self.weight_diff[ind2], w)
            if -(self.weight_diff[ind1] - self.weight_diff[ind2]) == w:
                return True
            else:
                return False
        else:
            #swap
            if self.par[root1] > self.par[root2]:
                root1, root2 = root2, root1
                ind1, ind2 = ind2, ind1
                w *= -1
            self.par[root1] += self.par[root2]
            self.par[root2] = root1
            self.weight_diff[root2] = w + self.weight_diff[ind1] - self.weight_diff[ind2]
            return True



n, m = list(map(int, input().split()))
query = []
for i in range(m):
    query.append(list(map(int, input().split())))
uf = weight_union_find(n)
for l, r, d in query:
    if not uf.unite(l-1, r-1, d):
        print("No")
        exit()
print("Yes")

Submission status: Accepted

Solution code:
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])



def func():
    x = [None for i in range(n)]
    for i in range(n):
        if x[i] == None:
            x[i] = 0
            q = [i]
        while q:
            j = q.pop()
            for k, d in graph[j]:
                if x[k] == None:
                    q.append(k)
                    x[k] = x[j] + d
                elif x[k] != x[j] + d:
                    return False
    return True

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

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
Info = [list(map(int, input().split())) for i in range(M)]

Group = [[i] for i in range(N+1)]  # 同じ集合に属する人のリスト
Distance = [[i, 0] for i in range(N+1)]  # 人を渡すと[親番号，親からの距離]が返る

for info in Info:
    l, r, d = info
    lp, rp = Distance[l][0], Distance[r][0]
    lpd, rpd = Distance[l][1], Distance[r][1]

    if lp != rp:
        if len(Group[lp]) > len(Group[rp]):
            Group[lp] += Group[rp]
            for h in Group[rp]:
                Distance[h][0] = lp
                Distance[h][1] += d + lpd - rpd
        else:
            Group[rp] += Group[lp]
            for h in Group[lp]:
                Distance[h][0] = rp
                Distance[h][1] -= d + lpd - rpd
    else:
        if rpd - lpd != d:
            print("No")
            exit()

print("Yes")

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    G[l - 1].append((r - 1, d))
    G[r - 1].append((l - 1, -d))
q = deque()

x = [None] * N


def _BFS(start):
    q.append(start)
    while len(q) != 0:
        p = q.popleft()
        for index, d in G[p]:
            if x[index] is None:
                x[index] = x[p] + d
                q.append(index)
            elif x[index] != x[p] + d:
                return False
    return True


def BFS():
    for i in range(N):
        if x[i] is None:
            x[i] = 0
            if not _BFS(i):
                return "No"
    return "Yes"


print(BFS())

Submission status: Accepted

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


class WeightedUnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.diff_weight = [0 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            root = self.find(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = root
            return root

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

    def union(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.par[y] = x
            self.diff_weight[y] = w

    def weight(self, x):
        self.find(x)
        return self.diff_weight[x]

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


uf = WeightedUnionFind(N)
ans = 'Yes'
for _ in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.is_same(L, R):
        if uf.diff(L, R) != D:
            ans = 'No'
            break
    else:
        uf.union(L, R, D)
print(ans)