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(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# x0を0に固定したときに各点への最短距離が求められて、それが矛盾しなければ良さそう
# 任意の点から初めて距離を埋めていく

N, M = read_ints()
LRD = []
graph = defaultdict(lambda: [])
for _ in range(M):
    l, r, d = read_ints()
    l -= 1
    r -= 1
    LRD.append((l, r, d))
    graph[l].append((r, d))
    graph[r].append((l, -d))


D = [INF] * N  # 各点の位置


def bfs(start):
    now, dist = start, 0
    que = deque([(now, dist)])
    D[now] = dist
    while que:
        now, dist = que.popleft()
        for to, co in graph[now]:
            to_dist = dist + co
            if D[to] != INF:
                if D[to] != to_dist:
                    print("No")
                    exit()
                continue
            D[to] = to_dist
            que.append((to, to_dist))


for i in range(N):
    if D[i] != INF:
        continue
    bfs(i)

print('Yes')

Submission status: Accepted

Solution code:
class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.weight = [0]*N

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

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

    def unite(self, x, y, w):
        w -= self.getWeight(x)
        w += self.getWeight(y)
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.weight[x] = self.weight[y]+w
            return

    def getWeight(self, x):
        x -= 1
        self.root(x)
        return(self.weight[x])


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

    N, M = map(int, input().split())
    G = unionFind(N)
    for i in range(M):
        L, R, D = map(int, input().split())
        if G.same(L, R):
            x = G.getWeight(L)
            y = G.getWeight(R)
            if x == y + D:
                continue
            else:
                print("No")
                exit(0)
        else:
            G.unite(L, R, D)
    print("Yes")


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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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))

ans = [None] * (N + 1)

def calc(i):
    ans[i] = 0
    stack = [i]
    while stack:
        now = stack.pop()
        for next_, d in G[now]:
            if ans[next_] == None:
                ans[next_] = ans[now] + d
                stack.append(next_)
            else:
                if ans[now] + d != ans[next_]:
                    return False
    return True

for i in range(1, N + 1):
    if ans[i] == None:
        if calc(i):
            pass
        else:
            print ('No')
            exit()


max_ = -10 ** 10
min_ = +10 ** 10
for i in ans[1:]:
    max_ = max(max_, i)
    min_ = min(min_, i)

if max_ - min_ > 10 ** 9:
    print ('No')
else:
    print ('Yes')

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()
    else:
        uf.unite(l,r,d)
print('Yes')

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L,R=L-1,R-1
    G[L].append((D,R))
    G[R].append((-D,L))
ok=True
dist=[None]*N
que=deque()
for i in range(N):
    if dist[i]!=None:
        continue
    que.append(i)
    dist[i]=0
    while que:
        v=que.popleft()
        for cost,nv in G[v]:
            if dist[nv]!=None:
                if dist[nv]!=dist[v]+cost:
                    print('No')
                    exit()
            else:
                dist[nv]=dist[v]+cost
                que.append(nv)

print('Yes')

Submission status: Accepted

Solution code:
def root(x):
    if(par[x]==x):
        return x
    else:
        r=root(par[x])
        diff_weight[x]+=diff_weight[par[x]]
        par[x]=r
        return r

def weight(x):
    root(x)
    return diff_weight[x]

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

def relate(a,b,w):
    w+=weight(a);w-=weight(b)
    a=root(a)
    b=root(b)
    if(a==b):
        return False
    if rank[a]<rank[b]:
        a,b=b,a
        w=-w
    if rank[a]==rank[b]:
        rank[b]+=1
        par[b]=a
    par[b]=a
    diff_weight[b]=w
    siz[a]+=siz[b]
    return True

def size(a):
    return siz[root(a)]
    
def same(a,b):
    return root(a)==root(b)
    
N,M=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]
diff_weight=[0 for _ in range(N)]

for i in range(M):
    L,R,D=map(int,input().split())
    L,R=L-1,R-1
    if same(L,R) and diff(L,R)!=D:
        print('No')
        exit()
    else:
        relate(L,R,D)
print('Yes')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    redge=[[] for _ in range(N)]
    for _ in range(M):
        l,r,d=map(int1,input().split())
        d+=1
        edge[l].append((r,d))
        edge[r].append((l,-d))
    s=0
    D=[-INF]*N
    used=[False]*N
    while True:
        for s in range(s,N):
            if not used[s]:
                break
        else:
            break
        D[s]=0
        stack=[s]
        while stack:
            v=stack.pop()
            used[v]=True
            for nv,d in edge[v]:
                if D[nv]==-INF:
                    D[nv]=D[v]+d
                else:
                    if D[nv]!=D[v]+d:
                        print('No')
                        exit()
                if not used[nv]:
                    stack.append(nv)
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    C = [[] for _ in range(N)]
    for _ in range(M):
        l, r, d = map(int, input().split())
        C[l - 1].append((r - 1, d))
        C[r - 1].append((l - 1, -d))
    INF = 10 ** 10
    P = [INF] * N
    def dfs(n, p, f):
        if P[n] != INF:
            if P[n] != p:
                return False
            return True
        P[n] = p
        for i, d in C[n]:
            if i == f:
                continue
            if not dfs(i, p + d, n):
                return False
        return True
            
    for i in range(N):
        if P[i] != INF:
            continue
        if not dfs(i, 0, -1):
            return False
    return True

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

Submission status: Accepted

Solution code:
from collections import deque


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

x = [None] + [None] * n
i = 0
while i < n:
    i += 1
    if x[i] is not None:
        continue

    q = deque()
    x[i] = 0
    q.append(i)
    while q:
        x1 = q.popleft()
        for x2, d in rels[x1]:
            if x[x1] is not None and x[x2] is not None:
                if x[x2] - x[x1] != d:
                    print('No')
                    exit()
                continue
            if x[x1] is not None and x[x2] is None:
                x[x2] = x[x1] + d
                q.append(x2)
            elif x[x1] is None and x[x2] is not None:
                x[x1] = x[x2] - d
                q.append(x1)

print('Yes')

Submission status: Accepted

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

import queue
q=queue.Queue()
for i in range(n):
    if dist[i] != inf: continue
    dist[i] = 0
    q.put((0,i))
    while not q.empty():
        cost, nown = q.get()
        for nextc, nextn in g[nown]:
            if dist[nextn] != inf:
                if dist[nextn] != cost + nextc:
                    print('No')
                    exit()
            else:
                dist[nextn] = cost+nextc
                q.put((dist[nextn], nextn))
print('Yes')

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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()}

N, M = MAP()

tree = WeightedUnionFind(N)

for _ in range(M):
	L, R, D = MAP()
	if not tree.is_same(L-1, R-1):
		tree.unite(L-1, R-1, D)
	else:
		if not tree.get_weight(L-1, R-1) == D:
			print("No")
			break
else:
	print("Yes")

Submission status: Accepted

Solution code:
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

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


    dis = [float("INF")]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append(x)
        while q:
            now = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == float("INF"):
                    dis[nex] = dis[now]+d
                    q.append(nex)
                else:
                    if dis[nex] != dis[now]+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == float("INF"):
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

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


    dis = [float("INF")]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append((x,0))
        while q:
            now,cnt = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == float("INF"):
                    dis[nex] = cnt+d
                    q.append((nex,cnt+d))
                else:
                    if dis[nex] != cnt+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == float("INF"):
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    from collections import deque
    # from heapq imort heappush, heappop
    inf = 10**18
    dist = [inf]*n

    for i in range(n):
        if dist[i] != inf:
            continue
        dist[i] = 0
        q = deque()
        q.append([i,0])
        while q:
            now,cnt = q.popleft()
            for nxt,nd in lines[now]:
                if dist[nxt] == inf:
                    dist[nxt] = cnt+nd
                    q.append([nxt,cnt+nd])
                    continue
                if dist[nxt] != cnt+nd:
                    print('No')
                    return 0
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class WeightedUnionFindTree:
    """Disjoint-Set Data Structure with weight

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n_nodes):
        self.par = [i for i in range(n_nodes)]  # parent
        self.rank = [0] * n_nodes  # depth of tree
        self.weights = [0] * n_nodes

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

    def unite(self, x, y, weight=0):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
            self.weights[root_x] = weight - self.weights[x] + self.weights[y]
        else:
            self.par[root_y] = root_x
            self.weights[root_y] = -weight - self.weights[y] + self.weights[x]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

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

    def diff(self, x, y):
        return self.weights[x] - self.weights[y]
import sys
n,m=map(int,input().split())
lrd=[]
tree = WeightedUnionFindTree(n)
for _ in range(m):
    lrd.append(list(map(int,input().split())))
for l,r,d in lrd:
    tree.unite(l-1,r-1,d)
    
for l,r,d in lrd:
    if tree.is_same(l-1,r-1):    
        if tree.diff(l-1,r-1) != d:
            print("No")
            sys.exit()
    else:
        tree.unite(l-1,r-1,d)
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
g = [[i,0] for i in range(N+1)]
g_num = [1 for i in range(N+1)]

def find(x,z):
    if g[x][0] == x: return x,z
    r,d = find(g[x][0],g[x][1])
    g[x] = [r,d]
    return g[x][0],g[x][1]+z

def union(x,y,d):
    if g_num[g[x][0]] < g_num[g[y][0]]:
        x,y = y,x; d = -d
    g_num[g[x][0]] += g_num[g[y][0]]
    g_num[g[y][0]] = 0
    g[g[y][0]][1] = g[x][1] + d - g[y][1]
    g[g[y][0]][0] = g[g[x][0]][0]


for _ in range(M):
    l,r,d = LI()

    if find(l,0)[0] == find(r,0)[0]:
        if g[l][1] + d != g[r][1]:
            print('No')
            exit(0)
    else:
        union(l,r,d)
print('Yes')

Submission status: Accepted

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  # 頂点、親
  q.append([i,-1])
  while q:
    v,parent = q.popleft()
    for child in E[v]:
      if child[0] == parent:
        continue
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append([child[0],v])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Submission status: Accepted

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  # 頂点、親
  q.append([i,-1])
  while q:
    v,parent = q.pop()
    for child in E[v]:
      if child[0] == parent:
        continue
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append([child[0],v])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Submission status: Accepted

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.popleft()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")

Submission status: Accepted

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

from collections import defaultdict
G = defaultdict(list)

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


pos = [float("inf") for _ in range(n)]
for i in range(n):
    if pos[i] == float("inf"):
        stack = [i]
        pos[i] = 0
    while stack:
        p = stack.pop()
        for a, d in G[p]:
            if pos[a] == float("inf"):
                pos[a] = pos[p] + d
                stack.append(a)

for i in range(n):
    for to, d in G[i]:
        if pos[to] - pos[i] != d:
            print("No")
            exit()

print("Yes")

Submission status: Accepted

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

dist = [[] for i in range(n)]

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


position = [10**10]*n
for i in range(n):
    if position[i]==10**10:
        stack = [i]
        position[i] = 0
        while stack:
            p = stack.pop()
            for to,d in dist[p]:
                if position[to]==10**10:
                    position[to]=position[p]+d
                    stack.append(to)

for i in range(n):
    for to,d in dist[i]:
        if position[to]-position[i]!=d:
            print('No')
            exit()
print('Yes')

Submission status: Accepted

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

N,M=map(int,input().split())
graph=[[] for _ in range(N)]

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

def BFD(x):
  global checked,answer,graph
  checked[x]=1
  for i,distance in graph[x]:
    if answer[i]=="first":
      answer[i]=answer[x]+distance
    else:
      if answer[i]!=answer[x]+distance:
        print("No")
        exit()
    
    if checked[i]==0:
      BFD(i)

checked=[0]*N
answer=["first"]*N

for i in range(N):
  if checked[i]==0:
    answer[i]=0
    BFD(i)

print("Yes")

Submission status: Accepted

Solution code:
import sys
import collections

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    LRD = [[int(x) for x in input().split()] for _ in range(M)]
    A = [[] for j in range(N + 1)]

    if M == 0:
        print("Yes")
        return

    slist = set()
    for l, r, d in LRD:
        A[l].append([r, d])
        A[r].append([l, -d])
        slist.add(l)
        slist.add(r)

    dmemo = [None] * (N + 1)

    f = False
    for i in list(slist):
        if dmemo[i] is not None:
            continue
        s = collections.deque()
        s.append(i)
        dmemo[i] = 0

        while s:
            c = s.pop()
            for r, d in A[c]:
                if dmemo[r] is not None:
                    if dmemo[r] - dmemo[c] != d:
                        f = True
                        break
                else:
                    dmemo[r] = dmemo[c] + d
                    s.append(r)
            if f:
                break
        if f:
            break

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

n,m=map(int,input().split())

lrd=[[] for _ in range(n)]

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

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    from collections import deque

    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = deque([])
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            L_R_D_arr.append(_)
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        iter_ = [float('inf')]*(N+1)
        iter_[L_R_D_arr[0][0]] = 0

        TF = 'No'
        rot_cnt = 0
        while len(L_R_D_arr)>0:
            if rot_cnt > len(L_R_D_arr):
                iter_ = [float('inf')]*(N+1)
                iter_[L_R_D_arr[0][0]] = 0
            else:
                L, R, D = L_R_D_arr[0]
                if iter_[L] == float('inf'):
                    if iter_[R] == float('inf'):
                        L_R_D_arr.rotate(-1)
                        rot_cnt += 1
                    else:
                        iter_[L] = iter_[R]-D
                        L_R_D_arr.popleft()
                        rot_cnt = 0
                else:
                    rot_cnt = 0
                    if iter_[R] == float('inf'):
                        iter_[R] = iter_[L]+D
                        L_R_D_arr.popleft()
                    elif iter_[R] == iter_[L]+D:
                        L_R_D_arr.popleft()
                    else:
                        break
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)


# 重み付きUnion-Find木
class Weighted_Union_Find():
    def __init__(self, N=1, SUM_UNITY=0):
        self.par  = [i for i in range(N)]  # 親ノード
        self.rank = [0] * N                # ランク
        self.diff_weight = [SUM_UNITY] * N 
    
    # 経路圧縮
    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            r = self.root(self.par[x])
            self.diff_weight[x] += self.diff_weight[self.par[x]]
            self.par[x] = r
            return r

    # 経路圧縮＋重みを返す
    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]
    
    # xとyが同じグループに属するか判定
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # xとyの属するグループを1つにまとめる
    def merge(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: 
            return False
        else:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
                w = -w
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.diff_weight[y] = w
            return True

    # xとyが同じグループにいるとき、xとyの重みの差を返す
    def diff(self,x,y):
        return self.weight(y) - self.weight(x)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = []
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            L_R_D_arr.append(_)
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        TF = 'No'
        wuf = Weighted_Union_Find(N)
        for L,R,D in L_R_D_arr:
            L -= 1
            R -= 1
            if wuf.issame(L,R):
                diff = wuf.diff(L,R)
                if diff != D:
                    break
            else:
                wuf.merge(L,R,D)
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)