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

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

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

pos = [None] * n

q = deque([0])
not_take = set(range(1,n))

ans = "Yes"

while q:
    
    a = q.popleft()
    if pos[a] is None:
        pos[a] = 0
    
    for b,dx in path[a]:
        
        if pos[b] is None:
            pos[b] = pos[a] + dx
            q.append(b)
            not_take.discard(b)
        elif pos[b] != pos[a] + dx:
            ans = "No"
            break
    if ans == "No": break
        
    if (not q) and (not_take != set()):
        q.append(not_take.pop())

if ans == "Yes" and max(pos) - min(pos) > 1e9:
    ans = "No"

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

Nvisited = set(range(N))
pos = dict()


def dfs(v):
    D = deque()
    D.append(v)
    pos[v] = 0
    while D:
        x = D.pop()
        for y, d in T[x]:
            if y in Nvisited:
                pos[y] = pos[x] + d
                Nvisited.remove(y)
                D.append(y)
            elif pos[y] - pos[x] != d:
                print('No')
                sys.exit()


while Nvisited:
    dfs(Nvisited.pop())

print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
T = [set() for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, input().split())
    T[l - 1].add((r - 1, d))
    T[r - 1].add((l - 1, -d))

Nvisited = set(range(N))
pos = dict()


def dfs(v):
    D = deque()
    D.append(v)
    pos[v] = 0
    while D:
        x = D.pop()
        for y, d in T[x]:
            if y in Nvisited:
                pos[y] = pos[x] + d
                Nvisited.remove(y)
                D.append(y)
            elif pos[y] - pos[x] != d:
                print('No')
                sys.exit()


while Nvisited:
    dfs(Nvisited.pop())

print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

# ----- Weighted Union Find -----
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
# ----- ----- -----

n,m = myinput()
lrd = [ list(myinput()) for _ in range(m) ]

wuf = WeightedUnionFind(n)

for i in range(m):
    l = lrd[i][0] - 1
    r = lrd[i][1] - 1
    d = lrd[i][2]
    if wuf.same(l,r):
        diff = wuf.diff(l,r)
        if d!=diff:
            print("No")
            exit()
        else:
            pass
    else:
        wuf.union(l,r,d)

print("Yes")
exit()

Submission status: Accepted

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

from collections import deque
que=deque([])
dist=[float('inf')]*n

for i in range(n):
    if dist[i]==float('inf'):
        dist[i]=int(0)
        que.append(i)
        while que:
            p=que.popleft()
            for d, j in es[p]:
                if dist[j]==float('inf'):
                    dist[j]=int(dist[p]+d)
                    que.append(j)

for l,r,d in lrd:
    if dist[l]-dist[r]!=-d:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

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

    #[行先, 距離]
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        l,r,d = map(int, input().split())
        adj[l-1].append([r-1, d])
        adj[r-1].append([l-1, -d])

    x = [inf]*n

    def bfs(v):
        if x[v]==inf:
            x[v] = 0
        d = deque([v])
        while d:
            v  = d.popleft()
            for nv, cost in adj[v]:
                if x[nv] == inf:
                    x[nv] = x[v] + cost
                    d.append(nv)
                else:
                    if x[nv] - x[v] != cost:
                        return False
        return True

    for v in range(n):
        if not bfs(v):
            print('No')
            exit()
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

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

    #[行先, 距離]
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        l,r,d = map(int, input().split())
        adj[l-1].append([r-1, d])
        adj[r-1].append([l-1, -d])

    x = [inf]*n

    def dfs(v):
        if x[v]==inf:
            x[v] = 0
        d = deque([v])
        while d:
            v  = d.popleft()
            for nv, cost in adj[v]:
                if x[nv] == inf:
                    x[nv] = x[v] + cost
                    d.append(nv)
                else:
                    if x[nv] - x[v] != cost:
                        return False
        return True


    for v in range(n):
        if not dfs(v):
            print('No')
            exit()
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ABC087D
# https://atcoder.jp/contests/abc087/tasks/arc090_b

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.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 d != Diff(l, r, par, diff_weight):
            print('No')
            exit()
print('Yes')

Submission status: Accepted

Solution code:
def main():
    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))
    dis = [0] * n
    visited = [False] * n
    stack = list(range(n))
    while len(stack):
        v = stack[-1]
        stack.pop()
        if visited[v]:
            continue
        visited[v] = True
        for u, d in g[v]:
            if not visited[u]:
                dis[u] = dis[v] + d
                stack.append(u)
    for v in range(n):
        for u, d in g[v]:
            if dis[v] + d != dis[u]:
                print('No')
                return
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(u):
    q = deque([[u, 0]])
    visited[u] = 0
    while q:
        u, dist = q.popleft()
        for next_u, d in tree[u]:
            next_x = dist + d
            if visited[next_u] is None:
                visited[next_u] = next_x
                q.append([next_u, next_x])
            elif visited[next_u] == next_x:
                continue
            else:
                print("No")
                exit()


for i in range(n):
    if visited[i] is None:
        bfs(i)
else:
    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))

INF = 10**18
minDist = [INF] * N
for s in range(N):
    if minDist[s] < INF:
        continue
    st = [s]
    minDist[s] = 0
    while st:
        now = st.pop()
        dist = minDist[now]
        for to, d in edges[now]:
            if minDist[to] == INF:
                minDist[to] = dist + d
                st.append(to)
                continue
            if minDist[to] != dist + d:
                print('No')
                exit()
print('Yes')

Submission status: Accepted

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

    ds = [-1] * N
    for i in range(N):
        if inn[i]: continue
        ds[i] = 0
        stk = [(i, 0)]
        while stk:
            v, d = stk.pop()
            for to, dt in G[v]:
                if ds[to] != -1:
                    if ds[to] != d+dt:
                        print('No')
                        return
                    continue
                ds[to] = d+dt
                stk.append((to, d+dt))

    if any([d == -1 for d in ds]):
        print('No')
        return
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    s, t, d = map(int, input().split())
    edge[s].append((t, d))
    edge[t].append((s, -d))

dist = [None] * (N + 1)


def isOK(v):
    node = [v]
    if dist[v] is None:
        dist[v] = 0

    while node:
        s = node.pop()
        for t, d in edge[s]:
            if dist[t] is None:
                dist[t] = dist[s] + d
                node.append(t)
            else:
                if dist[t] != dist[s] + d:
                    return False
    return True


ans = "Yes"
for i in range(1, N + 1):
    if dist[i] is not None:
        continue

    if not isOK(i):
        ans = "No"
        break
print(ans)

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 i in Q:
				for j,d in edge[i]:
					if ans[j]==10**10:
						P+=[j]
						ans[j]=ans[i]+d
			Q=P
for i in range(n):
	for j,k in edge[i]:
		if ans[i]+k!=ans[j]:print("No");exit()
print("Yes")

Submission status: Accepted

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

n, m =map(int, input().split())
g = [[] for _ 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))

s = []
visit = [-1]*n
dist = [False]*n
for i in range(n):
    if visit[i] == -1:
        s.append(i)
        visit[i] = 0
        dist[i] = 0
        while s:
            v = s.pop()
            for d, u in g[v]:
                if dist[u]:
                    if dist[u] != dist[v]+d:
                        print('No')
                        exit()
                if visit[u] == -1:
                    visit[u] = 0
                    dist[u] = dist[v]+d
                    s.append(u)
else:
    print('Yes')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10**10
# G[i][j] = iからjへの距離
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
# D[j] = jの属する連結成分のトップからjへの距離
D = [inf for i in range(n)]
# まだ探索していないiをトップとして探索する
for i in range(n):
    if D[i] != inf:
        continue
    Q = [i]
    D[i] = 0
    while Q:
        j = Q.pop()
        for k in G[j].keys():
            if D[k] == inf:
                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:
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:
import sys
N, M = map(int, input().split())
adj = [[] for _ in range(N)]

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

visited = [0]*N
dist = [0]*N

for i in range(N):
    if visited[i]:  # 探索したことのある(つまり矛盾がなかった)場所なら次の場所へ
        continue
    visited[i] = 1  # 探索したフラグを立てる
    stack = [i]  # 探索候補へ追加
    vset = set()  # 今回(iのターンで)探索する場所のリスト(という名のセット)

    while stack:
        v = stack.pop()  # 今探索する場所をvとする
        vset.add(v)  # 探索する場所を追加する
        for dest, d in adj[v]:
            if visited[dest]:
                continue
            visited[dest] = 1  # 探索したフラグ立てる
            dist[dest] = dist[v] + d  # 今回の情報でとりあえず距離を設定
            stack.append(dest)

    for v in vset:  # 今回探索した場所それぞれについて
        for dest, d in adj[v]:
            if dist[v] + d != dist[dest]:  # ほかの情報と矛盾するか
                print('No')  # 矛盾してたらNoとなる
                exit()

print('Yes')

Submission status: Accepted

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

for l, r, d in (map(int, l.split()) for l in sys.stdin):
    adj[l-1].append((r-1, d))
    adj[r-1].append((l-1, -d))

visited = [0]*N
dist = [0]*N

for i in range(N):
    if visited[i]:  # 探索したことのある(つまり矛盾がなかった)場所なら次の場所へ
        continue
    visited[i] = 1  # 探索したフラグを立てる
    stack = [i]  # 探索候補へ追加
    vset = set()  # 今回(iのターンで)探索する場所のリスト(という名のセット)

    while stack:
        v = stack.pop()  # 今探索する場所をvとする
        vset.add(v)  # 探索する場所を追加する
        for dest, d in adj[v]:
            if visited[dest]:
                continue
            visited[dest] = 1  # 探索したフラグ立てる
            dist[dest] = dist[v] + d  # 今回の情報でとりあえず距離を設定
            stack.append(dest)

    for v in vset:  # 今回探索した場所それぞれについて
        for dest, d in adj[v]:
            if dist[v] + d != dist[dest]:  # ほかの情報と矛盾するか
                print('No')  # 矛盾してたらNoとなる
                exit()

print('Yes')

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
D = [[]for _ in range(N)]
for i in range(M):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    D[l].append([r,d])
    D[r].append([l,-d])
# 負の重みを持つ辺があるので-1で初期化したdistでseen配列をかねようとするとダメ
INF = float('inf')
dist = [INF]*N
seen = [False]*N
q = deque([])
for s in range(N):
    if dist[s] != INF:
        continue
    q.append([s,0])
    while len(q) != 0:
        p = q.popleft()
        # print(p)
        # print(dist)
        #if dist[p[0]] != -1 and dist[p[0]] != p[1]: # 来たことがあって矛盾している場合
        if seen[p[0]] and dist[p[0]] != p[1]: # 来たことがあって矛盾している場合

            # print(p[0],dist[p[0]],p[1])
            print('No')
            exit()
        #if dist[p[0]] != -1 and dist[p[0]] == p[1]: # 来たことがあって矛盾していない場合
        if seen[p[0]] and dist[p[0]] == p[1]: # 来たことがあって矛盾していない場合
            continue
        dist[p[0]] = p[1]
        seen[p[0]] = True
        for np in D[p[0]]:
            q.append([np[0],p[1]+np[1]])
print('Yes')
#print(dist)

Submission status: Accepted

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

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


  #w[y]=w[x]+wとなるようにxとyを併合
  def unite(x,y,w):
      w += wei[x]-wei[y]
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
              w = -w
          par[x] += par[y]
          par[y] = x
          wei[y] = w
          return True

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

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

  import sys
  input = sys.stdin.readline  
  n,m = [int(i) for i in input().split()]
  par = [-1]*n
  wei = [0]*n

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

  print('Yes')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#重み付きUnion-Find

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

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


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

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

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)
  
import sys
input = sys.stdin.readline  
n,m = [int(i) for i in input().split()]
par = [-1]*n
wei = [0]*n

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

print('Yes')

Submission status: Accepted

Solution code:
#重み付きUnion-Find

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

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


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

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

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)
  
n,m = [int(i) for i in input().split()]
par = [-1]*n
wei = [0]*n

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

print('Yes')

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] = 0
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == 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())
ed = [[] for _ in range(n)]  # グラフ
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  # l -> r
  ed[r-1].append((l-1, -d))  # r -> l

visited = [False] * n  # 訪問フラグ（非連結の可能性の為）

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 _ in range(m):
  l,r,d=map(int,input().split())
  g[r-1].append((l-1,d))
  g[l-1].append((r-1,-d))
x=[None]*n
for i in range(n):
  if x[i]==None:
    x[i]=0
    dfs(i)
print('Yes')

Submission status: Accepted

Solution code:
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

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

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

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

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

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True
      
def main():
  n,m = map(int, input().split())
  uf = UF_weighed(n+1)
  for _ in range(m):
    a, b, c = map(int, input().split())
    if uf.same(a, b) and uf.diff(a, b) != c:
      return 'No'
    uf.merge(a, b, c)
  return 'Yes'

print(main())

Submission status: Accepted

Solution code:
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

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

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

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

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

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True
      
def main():
  n,m = map(int, input().split())
  uf = UF_weighed(n+1)
  for _ in range(m):
    a, b, c = map(int, input().split())
    if uf.same(a, b) and uf.diff(a, b) != c:
      return 'No'
    uf.merge(a, b, c)
  return 'Yes'

if __name__ == '__main__':
  print(main())

Submission status: Accepted

Solution code:
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

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

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

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

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

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True
      
def main():
  n,m = map(int, input().split())
  uf = UF_weighed(n+1)
  q = [tuple(map(int, input().split())) for _ in range(m)]
  for a, b, c in q:
    if uf.same(a, b) and uf.diff(a, b) != c:
      return 'No'
    uf.merge(a, b, c)
  return 'Yes'

if __name__ == '__main__':
  print(main())

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(u):
    que = deque([(u, 0)])
    X[u] = 0
    while que:
        u, x = que.popleft()
        for nu, add in graph[u]:
            nx = x + add
            if X[nu] == nx:
                continue
            if X[nu] is not None and X[nu] != nx:
                print('No')
                exit()
            X[nu] = nx
            que.append((nu, nx))


for i in range(N):
    if X[i] is None:
        bfs(i)
print('Yes')