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:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
        self.dist = [0 for _ in range(num)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
        elif self.dist[ry] != d + self.dist[x] - self.dist[y]:
            return False
        return True 
    

N, M = inpl()
X = UnionFind(N)
for _ in range(M):
    l, r, d = inpl()
    if not X.union(l-1, r-1, d):
        ans = 'No'
        break
else:
    ans = 'Yes'
print(ans)

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
        self.dist = [0 for _ in range(num)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y, d):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.par[ry] = rx
            self.dist[ry] = d + self.dist[x] - self.dist[y]
        elif self.dist[ry] != d + self.dist[x] - self.dist[y]:
            return False
        return True 
    

N, M = inpl()
X = UnionFind(N)
for _ in range(M):
    l, r, d = inpl()
    if not X.union(l-1, r-1, d):
        print('No')
        break
else:
    print('Yes')

Submission status: Wrong Answer

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

visited = set()
for i in range(1, N + 1):
    dist = {}
    dfs_stack = []
    if i not in visited:
        visited.add(i)
        dist[i] = 0
        dfs_stack.append(i)
    while dfs_stack:
        s = dfs_stack.pop()
        for t, d in edge[s]:
            if t in dist:
                if dist[t] != dist[s] + d:
                    print('No')
                    exit()
            else:
                dist[t] = dist[s] + d
            if t not in visited:
                visited.add(t)
                dfs_stack.append(t)

    if len(set(dist.keys())) != len(set(dist.values())):
        print('No')
        exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[0 for _ in range(n+1)]
o=[True for _ in range(n+1)]
for _ in range(m):
  a,b,c=map(int,input().split())
  if a>b:
    a,b=b,a
    c=-c
  if not (o[b]==False and o[b]==False):
    if o[b]==True:
      l[b]=l[a]+c
      o[b]=False
      o[a]=False
    elif o[a]==True:
      l[a]=l[b]-c
      o[a]=False
      o[b]=False
  else:
    if (l[b]-l[a])!=c:
      print("No")
      break
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[0 for _ in range(n+1)]
for _ in range(m):
  a,b,c=map(int,input().split())
  if a>b:
    a,b=b,a
    c=-c
  if not (l[a]!=0 and l[b]!=0):
    if not l[a]:
      l[a]=1
    l[b]=l[a]+c
  else:
    if (b-a)!=c:
      print("No")
      break
else:
  print("Yes")

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

setrecursionlimit(1000000)
N,M = list(map(int,input().split()))

edges = [[] for _ in range(N)]

for i in range(M):
    L,R,D = list(map(int,input().split()))
    edges[L - 1].append((R -1,D))
    edges[R - 1].append((L-1, -D))


visited = [None] * N
place = [0] * N
inf = 10 ** 10


def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (n,m) = (inf, - inf)
    for j,d in edges[i]:
        #print(j,d)
        if visited[j] and place[j] != place[i] + d:
            print("No")
            exit()
        place[j] = place[i] + d
        (x,y) = walk(j)
        (n,m) = (min(n,x),max(m,y))
    return (n,m)

'''
for i in range(N):
    if not visited[i]:
        place[i] = 0
    # 連結成分のminとmax
        (n,m) = walk(i)
        if m - n > 10 ** 9:
            print("No")
            exit()
'''
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**8)

def find(x):	#xの根を返す
	global table
	global diff_weight
	
	if table[x] == x:
		return x
	else:
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		table[x] = find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x) 
	x = find(x)	
	y = find(y)
	
	if x == y:
		return
	
	if rank[x] < rank[y]:
		x,y = y,x
		w = -w
	
	table[y] = x
	diff_weight[y] = w
	
	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]
		
def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))

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

table = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N)]	#木の長さ
diff_weight = [0 for i in range(N)]


for i in range(M):
	a,b,D = (map(int,input().split()))
	a -= 1
	b -= 1
	if check(a,b):
		if diff(a,b) != D:
			print('No')
			sys.exit()
	else:
		union(a,b,D)
	
	
print ('Yes')

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**8)

def find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x) 
	x = find(x)	
	y = find(y)
	
	if x == y:
		return
	
	if rank[x]<rank[y]:
		x,y = y,x
		w = -w
	
	table[y] = x
	diff_weight[y] = w
	
	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]
		
def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))

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

table = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N)]	#木の長さ
diff_weight = [0 for i in range(N)]


for i in range(M):
	a,b,D = (map(int,input().split()))
	a -= 1
	b -= 1
	if check(a,b):
		if diff(a,b) != D:
			print('No')
			sys.exit()
	else:
		union(a,b,D)
	
	
print ('Yes')

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**8)

def find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x) 
	x = find(x)	
	y = find(y)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
		diff_weight[y] = w
	else:
		w = -w
		table[x] = y
		diff_weight[x] = w
		if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]
		
def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return (weight(y) - weight(x))

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

table = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N)]	#木の長さ
diff_weight = [0 for i in range(N)]


for i in range(M):
	a,b,D = (map(int,input().split()))
	a -= 1
	b -= 1
	if check(a,b):
		if diff(a,b) != D:
			print('No')
			sys.exit()
	else:
		union(a,b,D)
	
	
print ('Yes')

Submission status: Wrong Answer

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

N,M = map(int,input().split())
Graph =[[] for i in range(N)]
for i in range(M):
    L,R,D = map(int,input().split())
    Graph[L-1].append((R-1,D))
    Graph[R-1].append((L-1 ,-D))
visit=[False]*N
for i in range(N):
    if visit[i]==False:
        visit[i]=1
        A = deque()
        A.append(i)
        while A:
            x = A.pop()
            for y,d in Graph[x]:
                if (visit[y] != False) and (visit[y]!=d+visit[x]):
                    print('No')
                    sys.exit()
                elif (visit[y] == False):
                    A.append(y)
                    visit[y]=d+visit[x] 
    
print('Yes')

Submission status: Wrong Answer

Solution code:
class WeightUnionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)
        self.weight=[0]*(number)

    def find(self,x):#親を探す xの親を示す
        if self.par[x] ==x:
            return x
        else:
            self.weight[x]+=self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def weighted(self,x):
        self.find(x)
        return self.weight[x]
    
    def union(self,x,y,w):#weight(y) = weight(x) + w となるように x と y をマージする
        w += self.weighted(x)
        w -= self.weighted(y)
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
            self.weight[px]=-w
        else:
            self.par[py]=px
            self.weight[py] = w
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
    
    def diff(self,x,y):
        return self.weight[y]-self.weight[x]
    
N,M = map(int,input().split())
Tree = WeightUnionfindtree(N)
ans = 'Yes'
for i in range(M):
    L,R,D = map(int,input().split())
    if Tree.connect(L-1,R-1):
        if Tree.diff(L-1,R-1)!=D:
            ans = 'No'
    else:
        Tree.union(L-1,R-1,D)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
temp = []
ans = [0]*(n+1)
flag = False
for i in range(m):
  l, r, d = map(int, input().split())
  if ans[r] == 0:
    ans[r] = ans[r-1] + d
  temp.append([l, r, d])

for i in temp:
  left, right, d = i
  if ans[right] - ans[left] != d:
    print('No')
    flag = True
    break

if flag == False:
  print('Yes')

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
dic_list = []
listind = [-1]*n
maxind = 0
for i in range(m):    
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if listind[l] == -1 and listind[r] == -1:
        listind[l] = maxind
        listind[r] = maxind
        dic_list.append({l : 0, r : d})
        maxind +=1
    elif listind[l] == listind[r]:
        dic_tmp = dic_list[listind[l]]
        if dic_tmp[r] - dic_tmp[l] != d:
            print('No')
            exit()
    elif listind[l] != -1 and listind[r] != -1:
        dicl = dic_list[listind[l]]
        dicr = dic_list[listind[r]]
        dicl[r] = dicl[l] + d
        offset = dicl[r] - dicr[r]
        for key in dicr:
            dicl[key] = dicr[key] + offset
            listind[key] = listind[l]
        print(dicl)
    elif listind[l] == -1 and listind[r] != -1:
        dic_tmp = dic_list[listind[r]]
        dic_tmp[l] = dic_tmp[r] - d
        listind[l] = listind[r]
    elif listind[l] != -1 and listind[r] == -1:
        dic_tmp = dic_list[listind[l]]
        dic_tmp[r] = dic_tmp[l] + d
        listind[r] = listind[l]
print('Yes')

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
dic_list = []
listind = [-1]*n
maxind = 0
for i in range(m):    
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    if listind[l] == -1 and listind[r] == -1:
        listind[l] = maxind
        listind[r] = maxind
        dic_list.append({l : 0, r : d})
        maxind +=1
    elif listind[l] == listind[r]:
        dic_tmp = dic_list[listind[l]]
        if dic_tmp[r] - dic_tmp[l] != d:
            print('No')
            exit()
    elif listind[l] != -1 and listind[r] != -1:
        dicl = dic_list[listind[l]]
        dicr = dic_list[listind[r]]
        dicl[r] = dicl[l] + d
        offset = dicl[r] = dicr[r]
        for key in dicr:
            dicl[key] = dicr[key] + offset
            listind[key] = listind[l]
    elif listind[l] == -1 and listind[r] != -1:
        dic_tmp = dic_list[listind[r]]
        dic_tmp[l] = dic_tmp[r] - d
        listind[l] = listind[r]
    elif listind[l] != -1 and listind[r] == -1:
        dic_tmp = dic_list[listind[l]]
        dic_tmp[r] = dic_tmp[l] + d
        listind[r] = listind[l]
print('Yes')

Submission status: Wrong Answer

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

checked = [0] * N
for i in range(N):
    if checked[i]: continue
    dist = [-1] * N
    dist[i] = 0
    stack = [i]
    while stack:
        v = stack.pop()
        checked[v] = 1
        for to,d in es[v]:
            if dist[to] < 0:
                dist[to] = dist[v] + d
                if not checked[to]:
                    stack.append(to)
            else:
                if dist[to] != dist[v] + d:
                    print('No')
                    exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
arcs = {}
for _ in range(M):
    l, r, d = tuple(map(int, input().split()))
    arcs[l, r] = d

def consistent(arcs):
    for (u, v), d in arcs.items():
        for w in range(1, N + 1): # u + 1, v
            if w == u or w == v:
                continue
            if (u, w) in arcs and (w, v) in arcs:
                if arcs[u, w] + arcs[w, v] != d:
                    return False
    return True

if consistent(arcs):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def consistent(arcs):
    for (u, v), d in arcs.items():
        for w in range(u + 1, v):
            if (u, w) in arcs and (w, v) in arcs:
                if arcs[u, w] + arcs[w, v] != d:
                    return False
    return True


def solve():
    N, M = map(int, input().split())
    arcs = {}
    for _ in range(M):
        l, r, d = tuple(map(int, input().split()))
        if l >= r:
            return False
        arcs[l, r] = d

    return consistent(arcs)


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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
arcs = {}
for _ in range(M):
    l, r, d = tuple(map(int, input().split()))
    arcs[l, r] = d

def consistent(arcs):
    for u, v in arcs.keys():
        for w in range(u + 1, v):
            if (u, w) in arcs and (w, v) in arcs:
                if arcs[u, w] + arcs[w, v] != arcs[u, v]:
                    return False
    return True

if consistent(arcs):
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys


class Node(object):
    def __init__(self):
        self.connected = []


def calc_dist(start, goal, dist_dict):
    dist = None
    visited = [start]
    queue = [(None, start)]
    while len(queue) > 0:
        frm = queue[0][0]
        to = queue[0][1]

        # 距離の調整
        if frm is None:
            dist = 0
        else:
            if (frm, to) in dist_dict:
                dist += dist_dict[(frm, to)]
            elif (to, frm) in dist_dict:
                dist -= dist_dict[(to, frm)]
            else:
                raise ValueError

        queue.remove(queue[0])
        if to == goal:
            return dist
        else:
            for n in to.connected:
                if n not in visited:
                    visited.append(n)
                    queue.append((to, n))
    return None


N, M = map(int, input().split())
nodes = [Node() for i in range(N + 1)]
D_dict = {}
id_set = set()

for i in range(M):
    L, R, D = map(int, input().split())
    if L in id_set and R in id_set:
        # 両方の数字が既出のとき，整合性チェック
        dist = calc_dist(nodes[L], nodes[R], D_dict)
        if dist is None:
            # 既存の関係でLからRに到達できないなら問題ない
            D_dict[(nodes[L], nodes[R])] = D
            nodes[L].connected.append(nodes[R])
            nodes[R].connected.append(nodes[L])
        else:
            # 既存の関係でLからRに到達できるなら整合性チェック
            if dist != D:
                print('No')
                sys.exit()

    else:
        # それ以外は問題ない
        id_set.add(L)
        id_set.add(R)
        D_dict[(nodes[L], nodes[R])] = D
        nodes[L].connected.append(nodes[R])
        nodes[R].connected.append(nodes[L])

print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
import copy
N,M=[int(i) for i in input().split(" ")]
if M==0:
    print("No")
    sys.exit()
x=[10**9+10 for i in range(N+1)]

LRD=[]


for i in range(M):
    LRD.append([int(i) for i in input().split(" ")])
consider=[LRD[0][0]]
x[LRD[0][0]]=0

while len(LRD)!=0:
    if len(consider)==0:
        consider=[LRD[0][0]]

    _consider=consider[0]
    _LRD=copy.deepcopy(LRD)
    for i in LRD:
        if i[0]==_consider:
            if x[i[1]]>10**9:
                x[i[1]]=x[i[0]]+i[2]
                if i[1] in consider:
                    pass
                else:
                    consider.append(i[1])
            elif x[i[1]]==x[i[0]]+i[2]:
                pass
            else:
                print("No")
                sys.exit()
            _LRD.remove(i)
        elif i[1]==_consider:
            if x[i[0]]>10**9:
                x[i[0]]=x[i[1]]-i[2]
                if i[0] in consider:
                    pass
                else:
                    consider.append(i[0])
            elif x[i[0]]==x[i[1]]-i[2]:
                pass
            else:
                print("No")
                sys.exit()
            _LRD.remove(i)
        else:
            pass
    consider.pop(0)
    LRD=_LRD
print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split())
a = []
for i in range(M):
    a.append(map(int, raw_input().split()))
x = [0 for i in range(N)]
y = [False for i in range(N)]
answer = 'Yes'
for i in range(M):
	L = a[i][0]
	R = a[i][1]
	D = a[i][2]
	if y[L-1] == False and y[R-1] == False:
		x[R-1] = x[L-1] + D
		y[L-1] = True
		y[R-1] = True
	elif y[L-1] == False and y[R-1] == True:
		x[L-1] = x[R-1] - D
		y[L-1] = True
	elif y[L-1] == True and y[R-1] == False:
		x[R-1] = x[L-1] + D
		y[R-1] = True
	elif y[L-1] == True and y[R-1] == True:
		if x[R-1] - x[L-1] != D:
			answer = 'No'
			break
print answer

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split())
a = []
for i in range(M):
    a.append(map(int, raw_input().split()))
x = [0 for i in range(N)]
y = [False for i in range(N)]
answer = 'Yes'
for i in range(M):
	L = a[i][0]
	R = a[i][1]
	D = a[i][2]
	if y[L-1] == False and y[R-1] == False:
		x[R-1] = x[L-1] + D
		y[L-1] = True
		y[R-1] = True
	elif y[L-1] == False and y[R-1] == True:
		x[L-1] = x[R-1] - D
		y[L-1] = True
	elif y[L-1] == True and y[R-1] == False:
		x[R-1] = x[L-1] + D
		y[R-1] = True
	elif y[L-1] == True and y[R-1] == True:
		if x[R-1] - x[L-1] == D:
			pass
		else:
			answer = 'No'
			break
print answer

Submission status: Wrong Answer

Solution code:
import numpy as np

def operation(infos):
  for i in xrange(len(infos)):
    for j in xrange(len(infos)):
      if(infos[j][0] == infos[i][1]):
        infos[i] = [infos[i][0],infos[j][1],infos[i][2]+infos[j][2]]
        print infos

def check(infos):
  for i in xrange(len(infos)):
    if(infos[i][0]==infos[i][1] and infos[i][2]!=0):
      return False
    for j in xrange(len(infos)):
      if(infos[i][0:2]==infos[j][0:2] and infos[i][2]!=infos[j][2]):
        return False
  return True
  


if __name__ == '__main__':

  # Get standard in
  n, m  = map(int, raw_input().split())
  infos = []
  for i in range(m):
    infos.append(map(int, raw_input().split()))

  print infos
  operation(infos)
  if(check(infos)):
    print 'Yes'
  else:
    print 'No'

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([[start]])
    q_d = deque([0])
    while(len(q) > 0):
        path = q.popleft()
        dist = q_d.popleft()
        w = path[len(path) - 1]
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist + x[1]
                new_path = path[:]
                new_path.append(x[0])
            elif dist_all[x[0]] != dist + x[1]:
                return False
            q.append(new_path)
            q_d.append(dist + x[1])
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, goal):
    q = [[start]]
    q_d = [0]
    d_set = set()
    while(len(q) > 0):
        path = q.pop(0)
        dist = q_d.pop(0)
        w = path[len(path) - 1]
        if w == goal:
            d_set.add(dist)
        else:
            for x in adj_list[w]:
                if x[0] not in path:
                    new_path = path[:]
                    new_path.append(x[0])
                    q.append(new_path)
                    q_d.append(dist + x[1])
    if len(d_set) == 1:
        return True
    else:
        return False
for i in range(n):
    for j in range(n):
        if not search(i, j):
            print('No')
            exit(0)
print('Yes')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]


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 weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.weight[px] = w - self.weighting(x) + self.weighting(y)
            else:
                self.par[py] = px
                self.weight[py] = -w - self.weighting(y) + self.weighting(x)
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.weight[px] = w - self.weighting(x) + self.weighting(y)
            else:
                self.par[py] = px
                self.weight[py] = -w - self.weighting(y) + self.weighting(x)
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.weight[px] = w - self.weighting(x) + self.weighting(y)
            else:
                self.par[py] = px
                self.weight[py] = -w - self.weighting(y) + self.weighting(x)
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.weight[px] = w - self.weight[x] + self.weight[y]
            else:
                self.par[py] = px
                self.weight[py] = -w - self.weight[y] + self.weight[x]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")
for i in range(N):
    wuf.find(i)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for i in range(M)]


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:
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 重さの検索
    def weighting(self, x):
        self.find(x)
        return self.weight[x]

    # 併合
    def union(self, x, y, w):
        w -= self.weighting(x)
        w += self.weighting(y)
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.weight[x] = w
        else:
            self.par[y] = x
            self.weight[y] = -w
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # 各頂点間の絶対距離
    def diff(self, x, y):
        return self.weighting(x) - self.weighting(y)


wuf = WeightedUnionFind(N)
for l, r, d in LRD:
    if wuf.same(l, r):
        if wuf.diff(l, r) != d:
            print("No")
            break
    else:
        wuf.union(l, r, d)
else:
    print("Yes")
for i in range(N):
    wuf.find(i)