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 Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
g = [[] for _ in range(n)]
for i in range(m):
    l,r,d = inpl()
    g[l-1].append((r-1,d))
    g[r-1].append((l-1,-d))
seen = [False] * n
dist = [0] * n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    while q:
        now = q.popleft()
        seen[i] = True
        for v,d in g[now]:
            if seen[v]:
                if dist[v] != d + dist[now] :
                    print('No')
                    quit()
            else:
                dist[v] = dist[now] + d
                seen[v] = True
                q.append(v)
print('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)

    # xからyへの重みの取得
    def get_weight(self, x, y):
        return self.weights[y] - self.weights[x]

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

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_parent_list(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, M = map(int, input().split())
    tree = WeightedUnionFind(N)
    flag = True
    for _ in range(M):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        if not tree.is_same(l, r):
            tree.unite(l, r, d)
        else:
            if tree.get_weight(l, r) == d:
                continue
            else:
                flag = False

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


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

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


    MIN = -10 ** 18

    lst = [MIN] * (N + 1)

    que = deque()
    que_append = que.append
    que_popleft = que.popleft

    for i in range(1, N + 1):
        if lst[i] == MIN:
            que_append(i)
            lst[i] = 0

        while que:
            tmp = que_popleft()
            for next_, d in G[tmp]:
                if lst[next_] == MIN:
                    lst[next_] = lst[tmp] + d
                    que_append(next_)
                    continue
                
                if lst[next_] == lst[tmp] + d:
                    continue
                else:
                    print ('No')
                    exit()

    print ('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

G = [[] for _ in range(N + 1)]

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


MIN = -10 ** 18

lst = [MIN] * (N + 1)

que = deque()
que_append = que.append
que_popleft = que.popleft

for i in range(1, N + 1):
    if lst[i] == MIN:
        que_append(i)
        lst[i] = 0

    while que:
        tmp = que_popleft()
        for next_, d in G[tmp]:
            if lst[next_] == MIN:
                lst[next_] = lst[tmp] + d
                que_append(next_)
                continue
            
            if lst[next_] == lst[tmp] + d:
                continue
            else:
                print ('No')
                exit()

print ('Yes')

Submission status: Accepted

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

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

G = [[] for _ in range(N + 1)]

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


MIN = -10 ** 18

lst = [MIN] * (N + 1)

que = deque()

for i in range(1, N + 1):
    if lst[i] == MIN:
        que.append(i)
        lst[i] = 0

    while que:
        tmp = que.popleft()
        for next_, d in G[tmp]:
            if lst[next_] == MIN:
                lst[next_] = lst[tmp] + d
                que.append(next_)
                continue
            
            if lst[next_] == lst[tmp] + d:
                continue
            else:
                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 + 1)]

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


MIN = -10 ** 18

lst = [MIN] * (N + 1)

que = deque()

for i in range(1, N + 1):
    if lst[i] == MIN:
        que.append(i)
        lst[i] = 0

    while que:
        tmp = que.popleft()
        for next_, d in G[tmp]:
            if lst[next_] == MIN:
                lst[next_] = lst[tmp] + d
                que.append(next_)
                continue
            
            if lst[next_] == lst[tmp] + d:
                continue
            else:
                print ('No')
                exit()

print ('Yes')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
import sys
input = sys.stdin.readline
INF = float("inf")


def check(g, n):
    visited = [False] * n
    dist = [INF] * n  # 最短距離を管理
    # 連結でない場合に備えて全頂点をスタートにする
    for s in range(n):
        if visited[s]:
            continue
        # 探索していなければBFSで探索開始
        que = deque([(0, s)])
        dist[s] = 0
        visited[s] = True
        while que:
            d, u = que.popleft()
            for nd, v in g[u]:
                nd += d
                if visited[v]:
                    #  すでに探索済みなら距離が一致しているか判定
                    if dist[v] != nd:
                        return False
                else:
                    # そうでなければ探索済みにしてqueに隣接頂点を追加
                    visited[v] = True
                    dist[v] = nd
                    que.append((nd, v))
    return True


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        l, r, d = map(int, input().split())
        l -= 1
        r -= 1
        # 重み付き有向グラフ
        g[l].append((d, r))  # (重み，頂点)で管理
        g[r].append((-d, l))  # 逆方向は-をつけることで有効グラフを表現
    if check(g, n):
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dist=[None]*n
from collections import deque
# 各頂点からの距離で矛盾が発生しないかシミュレーション
for i in range(n):
  q=deque()
  if dist[i]==None:
    dist[i]=0
    q.append(i)
  while q:
    cur=q.popleft()
    for nx,nxd in G[cur]:
      if dist[nx]==None:
        dist[nx]=dist[cur]+nxd
        q.append(nx)
      elif dist[nx]!=dist[cur]+nxd:
        print("No")
        exit(0)
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]


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    uf = WeightedUnionFind(N)
    LRD = [[int(i) for i in input().split()] for j in range(M)]
    for le, ri, d in LRD:
        if uf.same(le, ri):
            if uf.diff(le, ri) != d:
                return print("No")
        uf.union(le, ri, d)
    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    G=[[] for _ in range(N)]
    for _ in range(M):
        l,r,d=map(int, input().split())
        l,r=l-1,r-1
        G[l].append((r,d))
        G[r].append((l,-d))

    d=[0]*N
    used=[False]*N
    ans=True
    for i in range(N):
        if used[i]: continue
        used[i]=True
        stk=[(i,0)]
        while stk:
            v,vd=stk.pop()
            for to,td in G[v]:
                if used[to]:
                    if d[to]!=vd+td:
                        ans=False
                    continue
                used[to]=True
                d[to]=vd+td
                stk.append((to,d[to]))
    print('Yes' if ans else 'No')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Find(x, par, diff_weight):
    if par[x] < 0:
        return x
    else:
        px = Find(par[x], par, diff_weight)
        diff_weight[x] += diff_weight[par[x]]
        par[x] = px
        return px

def Unite(x, y, par, rank, diff_weight, w):
    w += diff_weight[x] - diff_weight[y]
    x = Find(x, par, diff_weight)
    y = Find(y, par, diff_weight)

    if x != y:
        if rank[x] < rank[y]:
            x, y =  y, x
            w = -w
        if rank[x] == rank[y]:
            rank[x] += 1
        par[x] += par[y]
        par[y] = x
        diff_weight[y] = w

def Same(x, y, par, diff_weight):
    return Find(x, par,diff_weight) == Find(y, par, diff_weight)

def Size(x, par, diff_weight):
    return -par[Find(x, par, diff_weight)]

def Weight(x, par, diff_weight):
    Find(x, par, diff_weight)
    return diff_weight[x]

def Diff(x, y, par, diff_weight):
    return Weight(y, par, diff_weight)  - Weight(x, par, diff_weight)

import sys
input = sys.stdin.buffer.readline
n, m = map(int, input().split())

par = [-1]*n
rank = [0]*n
diff_weight = [0]*n

for i in range(m):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    if not Same(l, r, par, diff_weight):
        Unite(l, r, par, rank, diff_weight, d)
    else:
        if Diff(l, r, par, diff_weight) != d:
            print('No')
            exit()
else:
    print('Yes')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ans=[10**10]*n
edge=[[]for _ in range(n)]
for _ in range(m):
  l,r,d=map(int,input().split())
  l-=1;r-=1
  edge[l].append((r,d))
  edge[r].append((l,-d))
for i in range(n):
  if ans[i]==10**10:
    ans[i]=0
    Q=[i]
    while Q:
      P=[]
      for j in Q:
        for k,d in edge[j]:
          if ans[k]==10**10:
            ans[k]=ans[j]+d
            P.append(k)
          elif ans[j]+d!=ans[k]:
            print("No");exit()
      Q=P
print("Yes")

Submission status: Accepted

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

for _ in range(M):
    fr, to, dist = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, dist))
    edges[to].append((fr, -dist))

def isOk():
    visited = [False] * N
    INF = 10**18
    minDist = [INF] * N
    for s in range(N):
        if visited[s]:
            continue
        st = [(s, 0)]
        minDist[s] = 0
        visited[s] = True
        while st:
            now, dist = st.pop()

            for to, d in edges[now]:
                d += dist
                if visited[to]:
                    if minDist[to] != d:
                        return False
                else:
                    visited[to] = True
                    minDist[to] = d
                    st.append((to, d))
    return True

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

class WeightedUnionFind():

    def __init__(self,N):
        self.N = N
        self.parents = [-1] * self.N
        self.diff_weight = [0] * self.N
    
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            p = self.find(self.parents[x])
            self.diff_weight[x] += self.diff_weight[self.parents[x]]
            self.parents[x] = p
            return p
    
    def weight(self,x):#xの親からの重みを返す
        self.find(x)
        return self.diff_weight[x]
    
    def diff(self,x,y):#同じグループにいたらxとyの重みの差を返す
        if self.find(x) == self.find(y):
            return self.weight(y) - self.weight(x)
        else:
            return 1e10

    def unite(self,x,y,w):#wieght(y) = weight(x) + dとなるように合体
        w += self.weight(x)
        w -= self.weight(y)

        x = self.find(x)
        y = self.find(y)
        if x == y:
            if self.diff(x,y) == w:
                return True
            else:
                return False

        if self.parents[x] > self.parents[y]:
            x,y = y,x
            w *= -1
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.diff_weight[y] = w
        return True
    
    def size(self,x):
        return - self.parents[self.find(x)]

def main():
    n,m = map(int,input().split())
    uf = WeightedUnionFind(n)
    flag = True
    for _ in range(m):
        l,r,d = map(int,input().split())
        l -= 1
        r -= 1
        if uf.unite(l,r,d):
            continue
        else:
            flag = False
            break
    print('Yes' if flag else 'No')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(20000000)


class WeightedUnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.parent = [i for i in range(n_nodes)]
        self.rank = [1] * n_nodes
        self.size = [1] * n_nodes
        # 重みの管理
        self.weight = [0] * n_nodes

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            y = self.find(self.parent[x])
            # 親までの重みを追加していく
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = y
            return self.parent[x]

    def unite(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] > self.rank[py]:
            self.parent[py] = px
            self.size[px] += self.size[py]
            self.weight[py] = -w - self.weight[y] + self.weight[x]
        else:
            self.parent[px] = py
            self.size[py] += self.size[px]
            self.weight[px] = w - self.weight[x] + self.weight[y]
            if self.rank[px] == self.rank[py]:
                self.rank[py] += 1

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

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

    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, M = map(int, input().split())
    Tree = WeightedUnionFind(N)
    for _ in range(M):
        L, R, D = map(int, input().split())
        if Tree.check(L - 1, R - 1):
            if Tree.diff(L - 1, R - 1) == D:
                continue
            else:
                print("No")
                return
        else:
            Tree.unite(L - 1, R - 1, D)
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

# DFS
seen = ['yet' for _ in range(n)]
todo = []
for i in range(n):
    if seen[i] != 'yet':
        continue
    seen[i] = 0
    todo.append(i)
    while todo != []:
        j = todo.pop(-1)
        for k in range(len(l[j])):
            if seen[l[j][k]] != 'yet':
                if seen[j] + d[j][k] != seen[l[j][k]]:
                    print('No')
                    exit()
                continue
            seen[l[j][k]] = seen[j] + d[j][k]
            todo.append(l[j][k])
print('Yes')

Submission status: Accepted

Solution code:
import sys
import io
import math
import string
# solution

sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v):
    ret = True
    for u, d in es[v]:
        if x[u] == None:
            x[u] = x[v] + d
            ret = ret and dfs(u)
        elif x[u] != x[v] + d:
            return False
    return ret

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    L, R, D = map(int, input().split())
    es[L].append((R, D))
    es[R].append((L, -D))
x = [None for i in range(N+1)]
flag = True
for v in range(1, N+1):
    if x[v] == None:
        x[v] = 0
        if dfs(v) == False:
            flag = False
            break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

uf=WeightedUnionFind(n)
for i in range(m):
    l,r,d=lrd[i]
    uf.union(l,r,d)
    # print(uf.par)
    # print(uf.weight)

for i in range(m):
    l,r,d=lrd[i]
    if not uf.same(l,r):
        print("No")
        break
    if uf.diff(l,r)!=d:
        print("No")
        break
else:
    print("Yes")

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
inf = 10 ** 10
edges = [[] for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    edges[l-1].append((r-1, d))
    edges[r-1].append((l-1, -d))

dist = [inf for _ in range(n)]

def dfs(v):
    stack = [v]
    dist[v] = 0

    while stack:
        v = stack.pop()
        d = dist[v]
        for to, cost in edges[v]:
            if dist[to] != inf:
                if dist[to] != d + cost:
                    return False
            else:
                dist[to] = d + cost
                stack.append(to)

    return True

flg = True
for i in range(n):
    if dist[i] == inf:
        if dfs(i) == False:
            flg = False
            break

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10**10
G = [{} for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    G[l-1][r-1] = d
    G[r-1][l-1] = -d
V = [False for i in range(n)]
D = [inf for i in range(n)]
for i in range(n):
    if V[i]:
        continue
    #hii 
    Q = [i]
    D[i] = 0
    while Q:
        j = Q.pop()
        V[j] = True
        for k in G[j].keys():
            if not V[k]:
                Q.append(k)
            if D[k] == inf:
                D[k] = D[j]+G[j][k]
            elif D[k] != D[j]+G[j][k]:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**5+1)
def dfs(p):
  for edge in g[p]:
    if x[edge[0]] is not None:
      if x[edge[0]]-x[p]!=edge[1]:
        print('No')
        exit()
    else:
      x[edge[0]]=x[p]+edge[1]
      dfs(edge[0])
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
  u,v,c=map(int,input().split())
  g[u-1].append((v-1,c))
  g[v-1].append((u-1,-c))
x=[None]*n
for i in range(n):
  if x[i]==None:
    x[i]=0
    dfs(i)
print('Yes')

Submission status: Accepted

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

class WeightedUnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.weight = [0] * (n + 1)

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            y = self.find(self.parent[x])
            self.weight[x] += self.weight[self.parent[x]]
            self.parent[x] = y
            return y

    def union(self, x, y, w):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
            self.weight[x_root] = w - self.weight[x] + self.weight[y]
        else:
            self.parent[y_root] = x_root
            self.weight[y_root] = - w - self.weight[y] + self.weight[x]
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

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


def main():
    N, M = map(int, input().split())
    wuf = WeightedUnionFind(N)
    for _ in range(M):
        l, r, d = map(int, input().split())
        if wuf.is_same(l, r):
            if wuf.diff(r, l) == d:
                continue
            else:
                print("No")
                sys.exit()
        else:
            wuf.union(r, l, d)
    print("Yes")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [None] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 1
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u] :
            if d[v] is None:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_ :
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, Dict, List, Tuple
except ImportError:
    pass
 
 
YESS = "Yes"  # type: str
NO = "No"  # type: str
 
 
def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    G = [[] for _ in range(N)]  # type: List[List[Tuple[int, int]]]
    for Li, Ri, Di in zip(L, R, D):
        Li -= 1
        Ri -= 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))
    pos = {}  # type: Dict[int, int]
    for i in range(N):
        if i in pos:
            continue
        q = deque()  # type: Deque[int]
        pos[i] = 0
        q.append(i)
        while q:
            s = q.popleft()
            for t, dst in G[s]:
                if t in pos:
                    if pos[t] != pos[s] + dst:
                        print(NO)
                        return
                    continue
                pos[t] = pos[s] + dst
                q.append(t)
    print(YESS)
 
 
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))
    solve(N, M, L, R, D)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [None] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 1
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] is None:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10**10
G = [{} for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    G[l-1][r-1] = d
    G[r-1][l-1] = -d
V = [False for i in range(n)]
D = [inf for i in range(n)]
for i in range(n):
    if V[i]:
        continue
    Q = [i]
    D[i] = 0
    while Q:
        j = Q.pop()
        V[j] = True
        for k in G[j].keys():
            if not V[k]:
                Q.append(k)
            if D[k] == inf:
                D[k] = D[j]+G[j][k]
            elif D[k] != D[j]+G[j][k]:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
import sys
try:
    from typing import Deque, Dict, List, Tuple
except ImportError:
    pass


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


def solve(N: int, M: int, L: "List[int]", R: "List[int]", D: "List[int]"):
    G = [[] for _ in range(N)]  # type: List[List[Tuple[int, int]]]
    for Li, Ri, Di in zip(L, R, D):
        Li -= 1
        Ri -= 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))
    pos = {}  # type: Dict[int, int]
    for i in range(N):
        if i in pos:
            continue
        q = deque()  # type: Deque[int]
        pos[i] = 0
        q.append(i)
        while q:
            s = q.popleft()
            for t, dst in G[s]:
                if t in pos:
                    if pos[t] != pos[s] + dst:
                        print(NO)
                        return
                    continue
                pos[t] = pos[s] + dst
                q.append(t)
    print(YES)


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))
    solve(N, M, L, R, D)


if __name__ == '__main__':
    main()