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: Wrong Answer

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,-R,D))
    merge(L,R)
  else:
    lrdlist.append((R,-L,-D))  
    merge(R,L)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

lrdlist2=[]
while(len(lrdlist)>0):
  lrdlist2=[]
  for L,R,D in lrdlist:
    R=-R
    if array[L]==-10**9:
      if array[R]==-10**9:
        lrdlist2.append((L,R,D))
      else:
        array[L]=array[R]-D
    else:
      if array[R]==-10**9:
        array[R]=array[L]+D
      else:
        if array[R]!=array[L]+D:
          print("No")
          sys.exit(0)
  lrdlist=lrdlist2

#print(array[1:])
print("Yes")

Submission status: Wrong Answer

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
    merge(L,R)
  else:
    lrdlist.append((R,L,-D))  
    merge(R,L)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

lrdlist2=[]
while(len(lrdlist)>0):
  lrdlist2=[]
  for L,R,D in lrdlist:
    if array[L]==-10**9:
      if array[R]!=-10**9:
        lrdlist2.append((L,R,D))
      else:
        array[L]=array[R]-D
    else:
      if array[R]==-10**9:
        array[R]=array[L]+D
      else:
        if array[R]!=array[L]+D:
          print("No")
          sys.exit(0)
  lrdlist=lrdlist2

#print(array[1:])
print("Yes")

Submission status: Wrong Answer

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
    merge(L,R)
  else:
    lrdlist.append((R,L,-D))  
    merge(R,L)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

for L,R,D in lrdlist:
  if array[L]==-10**9:
    if array[R]!=-10**9:
      #array[L]=0
      #array[R]=D
      None
    else:
      array[L]=array[R]-D
  else:
    if array[R]==-10**9:
      array[R]=array[L]+D
    else:
      if array[R]!=array[L]+D:
        print("No")
        break
else:
  #print(array[1:])
  print("Yes")

Submission status: Wrong Answer

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
    merge(L,R)
  else:
    lrdlist.append((R,L,-D))  
    merge(R,L)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

for L,R,D in lrdlist:
  if array[L]==-10**9:
    if array[R]!=-10**9:
      array[L]=0
      array[R]=D
    else:
      array[L]=array[R]-D
  else:
    if array[R]==-10**9:
      array[R]=array[L]+D
    else:
      if array[R]!=array[L]+D:
        print("No")
        break
else:
  #print(array[1:])
  print("Yes")

Submission status: Wrong Answer

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
  else:
    lrdlist.append((R,L,-D))  
  merge(L,R)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

for L,R,D in lrdlist:
  if array[L]==-10**9:
    if array[R]!=-10**9:
      array[L]=0
      array[R]=D
    else:
      array[L]=array[R]-D
  else:
    if array[R]==-10**9:
      array[R]=array[L]+D
    else:
      if array[R]!=array[L]+D:
        print("No")
        break
else:
  #print(array[1:])
  print("Yes")

Submission status: Wrong Answer

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

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
  else:
    lrdlist.append((R,L,-D))  
lrdlist.sort()
#print(lrdlist)

array=[0,0]+[-10**9]*(N-1)
for L,R,D in lrdlist:
  if array[L]==-10**9:
    if array[R]==-10**9:
      array[L]=0
      array[R]=D
    else:
      array[L]=array[R]-D
  else:
    if array[R]==-10**9:
      array[R]=array[L]+D
    else:
      if array[R]!=array[L]+D:
        print("No")
        break
else:
  #print(array[1:])
  print("Yes")

Submission status: Wrong Answer

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

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
  else:
    lrdlist.append((R,L,-D))  
lrdlist.sort()
#print(lrdlist)

array=[0,0]+[-10**9]*(N-1)
for L,R,D in lrdlist:
  if array[L]==-10**9:
    array[L]=0
    array[R]=D
  else:
    if array[R]==-10**9:
      array[R]=array[L]+D
    else:
      if array[R]!=array[L]+D:
        print("No")
        break
else:
  #print(array[1:])
  print("Yes")

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
n, m = map(int, input().split())
inf = 10**10
# G[i][j] = i
G = [{} for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    if l > r:
        l, r, d = r, l, -d
    G[l-1][r-1] = d
# D[j] = j
D = [inf for i in range(n)]
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():
            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: Wrong Answer

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())
    if l > r:
        l, r, d = r, l, -d
    G[l-1][r-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():
            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: Wrong Answer

Solution code:
n,m = map(int,input().split())
edges = [[] for i in range(n)]
for j in range(m):
  l,r,d = map(int,input().split())
  edges[l-1].append([r-1,d])
  edges[r-1].append([l-1,-d])
#エッジは3次元リストとして格納する
dist = [None for i in range(n+1)]
ans = "Yes"
def dfs(v):
  target_list = [v]
  if dist[v] == None:
    dist[v] = 0
  while target_list:
    target = target_list.pop()
    partners = edges[target-1]
    for partner in partners:
      num,d = partner[0],partner[1]
      #相手の距離が不明の場合はその地点も探索する
      if dist[num] == None:
        target_list.append(num)#ターゲットの追加
        dist[num] = dist[target] + d
      else:
         #すでに最短距離がわかっている場合はあっているかの確認
         if dist[num] != dist[target] + d:
            return False
    return True
  
for i in range(1,n+1):
  if dist[i] is not None:
    continue
  else:
    if not dfs(i):
      ans = "No"
      
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# 12:17-12:28 give up -> kaisetu
# 13:18-13:51 done


def main():
    N, M = map(int, input().split())
    L, R, D = [None] * M, [None] * M, [None] * M
    for i in range(M):
        L[i], R[i], D[i] = map(int, input().split())
        L[i] -= 1  # 1-index -> 0_index
        R[i] -= 1  # 1-index -> 0_index

    dist_infos = {}
    for l, r, d in zip(L, R, D):
        if l in dist_infos:
            dist_infos[l][r] = d
        else:
            dist_infos[l] = {r: d}

        if r in dist_infos:
            dist_infos[r][l] = -d
        else:
            dist_infos[r] = {l: -d}

    xs = [None] * N

    for i in range(N):
        if i not in dist_infos:
            continue

        if xs[i] is None:
            xs[i] = 0

        infos = {node: d for node, d in dist_infos[i].items() if node > i}

        for node, d in infos.items():
            if xs[node] is None:
                xs[node] = xs[i] + d
            elif xs[node] != xs[i] + d:
                return "No"

    return "Yes"


print(main())

Submission status: Wrong Answer

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

    for v in range(n):
        if x[v]==inf:
            x[v] = 0
        for nv, cost in adj[v]:
            if x[nv] == inf:
                x[nv] = x[v] + cost
            else:
                if x[nv] - x[v] != cost:
                    print('No')
                    exit()
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    for v in range(n):
        if x[v]==inf:
            x[v] = 0
        for nv, d in adj[v]:
            if x[nv] == inf:
                x[nv] = x[v] + d
            else:
                if x[nv] != x[v] + d:
                    print('No')
                    exit()
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
print('Yes')

Submission status: Wrong Answer

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())
    lrd = [list(map(int, input().split())) for _ in range(m)]
    # x[i]:i番目の人の相対位置
    x = [inf]*(n+1)

    for l, r, d in lrd:
        if x[l]==inf and x[r]==inf:
            x[l] = 0
            x[r] = d
        elif x[l] == inf :
            x[l] = x[r] - d
        elif x[r] == inf:
            x[r] = x[l] + d
        else:
            if x[r] - x[l] != d:
                print('No')
                exit()
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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())
    lrd = [list(map(int, input().split())) for _ in range(m)]
    # x[i]:i番目の人の相対位置
    x = [-inf]*(n+1)

    for l, r, d in lrd:
        if x[l]==inf and x[r]==inf:
            x[l] = 0
            x[r] = d
        elif x[l] == inf :
            x[l] = x[r] - d
        elif x[r] == inf:
            x[r] = x[l] + d
        else:
            if x[r] - x[l] != d:
                print('No')
                exit()
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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())
    lrd = [list(map(int, input().split())) for _ in range(m)]
    # x[i]:i番目の人の相対位置
    x = [-1]*(n+1)

    for l, r, d in lrd:
        if x[l]==-1 and x[r]==-1:
            x[l] = 0
            x[r] = d
        elif x[l] == -1 :
            x[l] = x[r] - d
        elif x[r] == -1:
            x[r] = x[l] + d
        else:
            if x[r] - x[l] != d:
                print('No')
                exit()
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dist=[float('inf')]*n
from collections import deque
def dfs():
    for s in range(n):
        if dist[s]==float('inf'):
            dist[s]=0
        if es[s]:
            q=deque([])
            q.append(s)
            while q:
                p=q.popleft()
                for newp, d in es[p]:
                    dist[newp]=dist[p]+d
        else:
            continue

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

Submission status: Wrong Answer

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

dist=[float('inf')]*n
from collections import deque
def dfs():
    for s in range(n):
        if es[s] and dist[s]==float('inf'):
            dist[s]=0
        if es[s]:
            q=deque([])
            q.append(s)
            while q:
                p=q.popleft()
                for newp, d in es[p]:
                    dist[newp]=dist[p]+d
        else:
            continue

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

Submission status: Wrong Answer

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

dist=[float('inf')]*n
from collections import deque
def dfs():
    for s in range(n):
        if es[s] and dist[s]==float('inf'):
            dist[s]=0
        if es[s]:
            q=deque([])
            q.append(s)
            while q:
                p=q.popleft()
                for newp, d in es[p]:
                    if dist[newp]==float('inf'):
                        dist[newp]=dist[p]+d
                    else: continue
        else:
            continue

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

Submission status: Wrong Answer

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

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

G = [[] for _ in range(N + 1)]
for el in LRD:
    l, r, d = el
    G[l].append((r, d))
#print(G)

seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True

    for child, dist in G[parent]:
        group[-1].append((parent, child, dist))
        if seen[child] == False:
            dfs(child)


group =[]
for i in range(1, N + 1):
    if seen[i] == False:
        group.append([])
        dfs(i)
#print(group)

mujun = 0
zahyo = [None] * (N + 1)
for lst in group:
    if len(lst) >= 3:
        zahyo[lst[0][0]] = 0
        for relation in lst:
            #print(zahyo)
            l, r, dist = relation
            if zahyo[r] != None:
                if zahyo[l] + dist != zahyo[r]:
                    mujun = 1
            else:
                zahyo[r] = zahyo[l] + dist

if mujun == 1:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D - People on a Line
# モジュールのインポート
import math

# 標準入力の取得
N,M = list(map(int, input().split()))
L,R,D = [],[],[]
for m in range(M):
    L_n,R_n,D_n = list(map(int, input().split()))
    L.append(L_n)
    R.append(R_n)
    D.append(D_n)

# 求解処理
# 与えられた情報に沿って、組（x_1, x_2, ・・・, x_N）を作成していき、矛盾が生じるかどうか判定する。
# 初期リストの作成
init_value = -1
x = [init_value for n in range(N)]

# x_L1 = 0で初期化
#if M >= 1:
#    x[L[0]-1] = 0

# 与えられた情報に沿って、各xを埋めていく
is_correct = True
for i in range(M):
    if x[L[i]-1] == init_value:
        x[L[i]-1] = 0
    x_Ri = x[L[i]-1] + D[i]
    # 矛盾があるかどうか判定
    if (x[R[i]-1] != init_value) and (x[R[i]-1] != x_Ri):
        is_correct = False
        break
    x[R[i]-1] = x_Ri

# 結果出力
if is_correct:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

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

G = [[] for _ in range(N + 1)]
for el in LRD:
    l, r, d = el
    G[l].append((r, d))
#print(G)

seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True

    for child, dist in G[parent]:
        group[-1].append((parent, child, dist))
        if seen[child] == False:
            dfs(child)


group =[]
for i in range(1, N + 1):
    if seen[i] == False:
        group.append([])
        dfs(i)
#print(group)

mujun = 0
for lst in group:
    if len(lst) >= 3:
        dct = {}
        dct[lst[0][0]] = 0
        for relation in lst:
            l, r, dist = relation
            if r in dct:
                if dct[l] + dist != dct[r]:
                    mujun = 1
            else:
                dct[r] = dct[l] + dist

if mujun == 1:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D - People on a Line
# モジュールのインポート
import math

# 標準入力の取得
N,M = list(map(int, input().split()))
L,R,D = [],[],[]
for m in range(M):
    L_n,R_n,D_n = list(map(int, input().split()))
    L.append(L_n)
    R.append(R_n)
    D.append(D_n)

# 求解処理
# 与えられた情報に沿って、組（x_1, x_2, ・・・, x_N）を作成していき、矛盾が生じるかどうか判定する。
# 初期リストの作成
init_value = -1
x = [init_value for n in range(N)]

# x_L1 = 0で初期化
if M >= 1:
    x[L[0]-1] = 0

# 与えられた情報に沿って、各xを埋めていく
is_correct = True
for i in range(M):
    x_Ri = x[L[i]-1] + D[i]
    # 矛盾があるかどうか判定
    if (x[R[i]-1] != init_value) and (x[R[i]-1] != x_Ri):
        is_correct = False
        break
    x[R[i]-1] = x_Ri

# 結果出力
if is_correct:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    LRD = [[int(i) for i in input().split()] for j in range(M)]
    par = [i for i in range(N)]
    rank = [1]*N
    weight = [0]*N

    def find_root(x):
        if par[x] == x:
            return x
        else:
            r = find_root(par[x])
            weight[x] += weight[par[x]]
            par[x] = r
            return r

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y, w):
        w += weight[x]
        w -= weight[y]
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x
        weight[y] += w

    def size(x):
        return rank[find_root(x)]

    def get_weight(x):
        find_root(x)
        return weight[x]

    def get_diff(x, y):
        return get_weight(x) - get_weight(y)

    for le, ri, d in LRD:
        le, ri = le-1, ri-1
        if is_same_group(le, ri):
            if get_diff(ri, le) != d:
                return print("No")
        else:
            if le < ri:
                unite(le, ri, d)
            else:
                unite(le, ri, -d)
    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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())
    if l > r:
        l, r, d = r, l, -d
    G[l-1][r-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():
            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: Wrong Answer

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())
    if l > r:
        l, r, d = r, l, -d
    G[l-1][r-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)
                D[k] = D[j]+G[j][k]
            elif D[k] != D[j]+G[j][k]:
                print('No')
                exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
min_dest = n-1

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))
    min_dest = min(min_dest, l-1, r-1)

d = [-1]*n  # 基準点から各点までの距離
d[min_dest] = 0  # 基準点をスタート地点とするため距離を0に設定

stack = [min_dest] # 探索候補。スタート地点である基準点を先に積んでおく。
ans = "Yes"
while stack:
    now = stack.pop()
    for dest, dist in adj[now]:
        if d[dest] == -1:
            d[dest] = d[now] + dist
            stack.append(dest)
        elif d[dest] != d[now] + dist:
            # print('d[dest]', d[dest], 'd[now]', d[now], 'dist', dist)
            ans = "No"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ed = [[] for _ in range(n)]  # グラフ
v = [float('inf')] * 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 = [0] * 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] == float('inf'):
          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: Wrong Answer

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 = [0] * 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] == 0:
          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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
from copy import deepcopy
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    edge[x].append([y,z])
    #edge[y].append([x,-z])

dist = [-1] * N
ans = ["Yes"]
def dfs(pv, v, d):
    if dist[v] < 0:
        dist[v] = d
    elif dist[v] != d and dist[v] > 0:
        ans[0] = "No"

    for i, nv in enumerate(edge[v]):
        if pv == nv[0]:
            continue
        if nv[1] == 10 ** 9:
            continue
        nd = edge[v][i][1]
        edge[v][i][1] = 10 ** 9
        dfs(v, nv[0], d+nd)

for i in range(N):
    if dist[i] == -1:
        dfs(-1,i,0)

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
from copy import deepcopy
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    edge[x].append([y,z])
    edge[y].append([x,-z])

dist = [-1] * N
ans = ["Yes"]
def dfs(pv, v, d):
    if dist[v] < 0:
        dist[v] = d
    elif dist[v] != d and dist[v] > 0:
        ans[0] = "No"

    for i, nv in enumerate(edge[v]):
        if pv == nv[0]:
            continue
        if nv[1] == 10 ** 9:
            continue
        nd = edge[v][i][1]
        edge[v][i][1] = 10 ** 9
        dfs(v, nv[0], d+nd)

for i in range(N):
    if dist[i] == -1:
        dfs(-1,i,0)

print(*ans)