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:
n,m = map(int,input().split())
branch = dict()
arrival = dict()
goal = dict()
for i in range(n):
	branch[i+1] = []
	arrival[i+1] = []
	goal[i+1] = []
for i in range(m):
	l,r,d = map(int,input().split())
	branch[l].append([r,d])
	branch[r].append([l,-d])
	arrival[l].append([r,0])
	arrival[r].append([l,0])
	goal[l].append([r,1])
	goal[r].append([l,1])

distarrival = [0 for i in range(n+1)]
q = [1]
distarrival[1] = 1

i = 1
check = True
flag = True
while arrival != goal:
	if flag and len(q) == 0:
		for k in range(len(arrival[i])):
			if arrival[i][k][1] == 0:
				q.append(arrival[i][k][0])
		i += 1
	elif flag:
		next = branch[q[0]]
		for k in range(len(next)):
			if arrival[q[0]][k][1] == 0:
				arrival[q[0]][k][1] = 1
				ind = 0
				while q[0] != arrival[arrival[q[0]][k][0]][ind][0]:
					ind += 1
				arrival[arrival[q[0]][k][0]][ind][1] = 1
				if distarrival[next[k][0]] == 0 or distarrival[q[0]] == 0:
					distarrival[next[k][0]] = distarrival[q[0]] + next[k][1]
				else:
					if distarrival[next[k][0]]-distarrival[q[0]] != next[k][1]:
						check = False
						flag = False
						break
			else:
				if distarrival[next[k][0]] - distarrival[q[0]] != next[k][1]:
					check = False
					flag = False
					break
		q.pop(0)
	else:
		break
if check:
	print('Yes')
else:
	print('No')

Submission status: Wrong Answer

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

check = True
x = [None for i in range(n+1)]
for i in branch:
	temp = [i]
	if x[i] == None:
		x[i] = 0
		tempcheck = True
		for k in range(len(branch[i])):
			if x[branch[i][k][0]] == None:
				x[branch[i][k][0]] = x[i] + branch[i][k][1]
				temp.append(branch[i][k][0])
			else:
				if branch[i][k][1] == x[branch[i][k][0]] - x[i]:
					tempcheck = False
				else:
					if tempcheck:
						for e in range(len(temp)):
							x[temp[e]] = x[temp[e]] + (x[branch[i][k][0]]-x[i]-branch[i][k][1])
					else:
						check = False
						break
	else:
		for k in range(len(branch[i])):
			if x[branch[i][k][0]] == None:
				x[branch[i][k][0]] = x[i] + branch[i][k][1]
				temp.append(branch[i][k][0])
			else:
				if branch[i][k][1] != x[branch[i][k][0]] - x[i]:
					check = False
					break
if check:
	print('Yes')
else:
	print('No')

Submission status: Wrong Answer

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


class WeightedUnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.diff_weight = [0 for i in range(n)]

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

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

    def union(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.par[y] = x
            self.diff_weight[y] = w

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

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


uf = WeightedUnionFind(N)
ans = 'Yes'
for _ in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.is_same(L, R):
        if uf.diff(L, R) != D:
            ans = 'No'
            break
    else:
        uf.union(L, R, D)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [input().split() for l in range(M)]
dict = {}
for i in range(1,N+1):
  dict[i] = -1
a= sorted(a)
ans = "Yes"
for i in range(M):
  ti = int(a[i][0])
  dai = int(a[i][1])
  sa = int(a[i][2])
  if dict[ti] == -1:
    dict[ti] = 0
  if dict[dai] != -1 and dict[ti] != -1:
    if dict[dai] != dict[ti] + sa:
      ans = "No"
      break
  dict[dai] = dict[ti] + sa
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [input().split() for l in range(M)]
dict = {}
for i in range(1,N+1):
  dict[i] = -1
a= sorted(a)
ans = "Yes"
for i in range(M):
  ti = int(a[i][0])
  dai = int(a[i][1])
  sa = int(a[i][2])
  if dict[ti] == -1:
    dict[ti] = 0
  if dict[dai] != -1 and dict[dai] != -1:
    if dict[dai] != dict[ti] + sa:
      ans = "No"
  dict[dai] = dict[ti] + sa
print(ans)

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):
        return self.weight[x]
    
    def union(self,x,y,w):#weight(y) = weight(x) + w となるように x と y をマージする
        w += self.weight[x]
        w -= self.weight[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())

parent = [i for i in range(N+1)]
distance = [0 for i in range(N+1)]
depth = [1 for i in range(N+1)]

def root(x):
    if x == parent[x]:
        return x
    else:
        return root(parent[x])

def to_root(x):
    if x == parent[x]:
        return 0
    else:
        return distance[x] + to_root(parent[x])

for _ in range(M):
    L, R, D = map(int, input().split())
    if root(L) == root(R):
        l = to_root(L)
        r = to_root(R)
        if D != r-l:
            print("No")
            exit()
    else:
        if depth[L] < depth[R]:
            L,R = R,L
            D = -D
        rootL = root(L)
        parent[R] = rootL
        distance[R] = to_root(L)+D

        depth[rootL] = max(rootL, depth[R]+1)
print("Yes")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
INF = 10**9+1

parent = [i for i in range(N+1)]
distance = [0 for i in range(N+1)]
depth = [1 for i in range(N+1)]

def root(x):
    if x == parent[x]:
        return x
    else:
        return root(parent[x])

def to_root(x):
    if x == parent[x]:
        return 0
    else:
        return distance[x] + to_root(parent[x])

for _ in range(M):
    L, R, D = map(int, input().split())
    if root(L) == root(R):
        l = to_root(L)
        r = to_root(R)
        if D != r-l:
            print("No")
            exit()
    else:
        if depth[L] < depth[R]:
            L,R = R,L
            D = -D
        parent[R] = root(L)
        distance[R] = to_root(L)+D
        depth[L] = max(depth[L], depth[R]+1)
print("Yes")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
INF = 10**9+1

parent = [i for i in range(N+1)]
distance = [0 for i in range(N+1)]
depth = [1 for i in range(N+1)]

def root(x):
    if x == parent[x]:
        return x
    else:
        return root(parent[x])

def to_root(x):
    if x == parent[x]:
        return 0
    else:
        return distance[x] + to_root(parent[x])

for _ in range(M):
    L, R, D = map(int, input().split())
    if root(L) == root(R):
        l = to_root(L)
        r = to_root(R)
        if D != l-r:
            print("No")
            exit()
    else:
        if depth[L] < depth[R]:
            L,R = R,L
            D = -D
        parent[L] = R
        distance[L] = D
        depth[L] = max(depth[L], depth[R]+1)
print("Yes")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
INF = 10**9+1

parent = [i for i in range(N+1)]
distance = [0 for i in range(N+1)]
depth = [1 for i in range(N+1)]

def root(x):
    if x == parent[x]:
        return x
    else:
        return root(parent[x])

def to_root(x):
    if x == parent[x]:
        return 0
    else:
        return distance[x] + to_root(parent[x])

for _ in range(M):
    L, R, D = map(int, input().split())
    if root(L) == root(R):
        l = to_root(L)
        r = to_root(R)
        if D != l-r:
            print("No")
            exit()
    else:
        if depth[L] < depth[R]: L,R = R,L
        parent[L] = R
        distance[L] = D
        depth[L] = max(depth[L], depth[R]+1)
print("Yes")

Submission status: Wrong Answer

Solution code:
def sub(a, b, n):
 r = a[:]
 for i in range(len(b)):
  r[i] -= b[i] * n
 return r
def mult(a, n):
 r = a[:]
 for i in range(len(a)):
  r[i] *= n
 return r

def pm(matr):
 for i in range(len(matr)):
  print matr[i]
 print ""
 return ""

def rref(matr):
 pivotCt = 0
 for d in range(max(len(matr), len(matr[0])-1)):
  print d, pivotCt
  pm(matr)
  #scan for first pivot
  pivot = None
  for i in range(len(matr)):
   allZeroes = True
   for j in range(d):
    if matr[i][j] != 0:
     allZeroes = False
     break
   if matr[i][d] != 0 and allZeroes:
    pivot = mult(matr[i], 1/matr[i][d])
    del matr[i]
    matr.insert(pivotCt, pivot)
    break
  if pivot != None:
   for i in range(len(matr)):
    if i != pivotCt and matr[i][d] != 0:
     matr[i] = sub(matr[i], pivot, matr[i][d])
   pivotCt += 1
 return matr

s = raw_input().split(" ")
vs = int(s[0])
es = int(s[1])


if es == 0:
 print "Yes"
else:
 matr = []
 for i in range(es):
  matr.append([0] * (vs + 1))
  q = raw_input().split(" ")
  x = int(q[0])
  y = int(q[1])
  z = int(q[2])
  matr[i][x] = 1
  matr[i][y] = -1
  matr[i][-1] = z

 matr = rref(matr)
 print matr
 bad = False
 for i in range(len(matr)):
  allZeroes = True
  for j in range(len(matr[0])-1):
   if matr[i][j] != 0:
    allZeroes = False
    break
  print allZeroes, matr[i][-1]
  if allZeroes and matr[i][-1] != 0:
    bad = True
    break

 if bad:
  print "No"
 else:
  print "Yes"

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n+1) ]
dist=[None for i in range(n+1)]
dist[0]=0
result=[True]

for i in range(m):
    l,r,d=(int(i) for i in input().split())
    graph[l].append((r,-d))
    graph[r].append((l,d))
def haba(i):
    if dist[i]== None:
        stack=[]
        dist[i]=0
        stack.append(i)
        while len(stack)!=0 :
            l=stack.pop()
            for r,d in graph[l]:
                b=dist[l]+d
                if dist[r]==None :
                    dist[r]=b
                    stack.append(r)
                elif dist[r]!=b:
                     result[0]=False
                     return
        return 
    else:
        return 

for i in range(n+1):
    haba(i)
    if not result[0]:
        print('No')
        break
print('Yes')

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for i in range(M) ]
x = [-1]*(N+1)
unsolve = LRD

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

def sr(unsolves):
    nextUnsolve = []
    for u in unsolves:
        l, r, d = u
        if x[l] == -1 and x[r] == -1:
            nextUnsolve.append(u)
        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()
    if len(nextUnsolve) != 0 and unsolves != nextUnsolve :
        sr(nextUnsolve)

x[LRD[0][0]] = 0
sr(unsolve)

print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [None]*(N+1)

contradiction = False

for i in range(M):
    l, r, d = map(int, input().split())
    if X[l] == None:
        X[l] = 0
    temp = X[l] + d
    if X[r] == None or X[r] >= temp:
        X[r] = temp
    else:
        contradiction = True

max_coord = 0
for x in X:
    if x is not None and x > max_coord:
        max_coord = x

if max_coord > 10**9:
    contradiction = True
        
if contradiction:
    print("No")
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)]
h_list = ["NaN"]*(N+1)
for i in range(M):
    if h_list[LRD[i][0]] == "NaN" and h_list[LRD[i][1]] == "NaN":
        h_list[LRD[i][0]] = 0
        h_list[LRD[i][1]] = LRD[i][2]
    elif h_list[LRD[i][0]] == "NaN":
        h_list[LRD[i][0]] = h_list[LRD[i][1]] - LRD[i][2]
    elif h_list[LRD[i][1]] == "NaN":
        h_list[LRD[i][1]] = h_list[LRD[i][0]] + LRD[i][2]
    elif h_list[LRD[i][0]] != h_list[LRD[i][1]] - LRD[i][2]:
        print('No')
        exit()
print('Yes')

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:
N, M = list(map(int, input().split()))
none = 10000000000000000
x = [none for i in range(N)]
for i in range(M) :
    l, r , d = list(map(int, input().split()))
    l -= 1
    r -= 1
    if x[l] == none and x[r] == none :
        x[l] = 0
        x[r] = d
    elif x[l] == none :
        x[l] = x[r] - d
    elif x[r] == none :
        x[r] = x[l] + d
    elif x[l] + d != x[r] :
        print("No")
        quit()
print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
x = [-1 for i in range(N)]
for i in range(M) :
    l, r , d = list(map(int, input().split()))
    l -= 1
    r -= 1
    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
    elif x[l] + d != x[r] :
        print("No")
        quit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

poses = np.zeros(N + 1, 'i')
visited = np.zeros(N + 1, np.bool)
error = False
for (i, j, d) in DISTS:
    if not visited[i]: poses[i] = 0
    visited[i] = True
    value = poses[i] + d
    if not visited[j]:
        visited[j] = True
        poses[j] = value
    elif poses[j] != value:
        error = True
        break

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

INF = 10000 * 100000 * 10
poses = np.empty(N + 1, 'i')
poses[:] = INF
error = False
for (i, j, d) in DISTS:
    if poses[i] == INF: poses[i] = 0
    value = poses[i] + d
    if poses[j] == INF:
        poses[j] = value
    elif poses[j] != value:
        error = True
        break

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

INF = 10000000000
poses = np.zeros(N + 1, 'i')
poses[:] = INF
for (i, j, d) in DISTS:
    if poses[i] == INF: poses[i] = 0
    value = poses[i] + d
    if poses[j] == INF:
        poses[j] = value
    elif poses[j] != value:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

INF = 1000000000
poses = np.zeros(N + 1, 'i')
poses[:] = INF
#print(DISTS)
for (i, j, d) in DISTS:
    if poses[i] == INF: poses[i] = i * 200000
    value = poses[i] + d
    if poses[j] == INF:
        poses[j] = value
    elif poses[j] != value:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

INF = 100000000
poses = np.zeros(N + 1, 'i')
poses[:] = INF
print(DISTS)
for (i, j, d) in DISTS:
    if poses[i] == INF: poses[i] = i * 20000
    value = poses[i] + d
    if poses[j] == INF:
        poses[j] = value
    elif poses[j] != value:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

INF = 10000000000
poses = np.zeros(N + 1, 'i')
poses[:] = INF
print(DISTS)
for (i, j, d) in DISTS:
    if poses[i] == INF: poses[i] = i * 200000
    value = poses[i] + d
    if poses[j] == INF:
        poses[j] = value
    elif poses[j] != value:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

INF = 10000000
poses = np.zeros(N + 1, 'i')
poses[:] = INF
for (i, j, d) in DISTS:
    if poses[i] == INF: poses[i] = 0
    value = poses[i] + d
    if poses[j] == INF:
        poses[j] = value
    elif poses[j] != value:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
DISTS = np.array([list(map(int, input().split())) for _ in range(M)], 'i')
for i, (j0, j1, d) in enumerate(DISTS):
    if j0 > j1:
        DISTS[i, 0], DISTS[i, 1] = j1, j0
        DISTS[i, 2] = -d
if len(DISTS) > 0:
    ind = np.argsort(DISTS[:, 0])
    DISTS = DISTS[ind]

INF = 10000000
poses = np.zeros(N + 1, 'i')
poses[:] = INF
poses[1] = 0
for (i, j, d) in DISTS:
    if poses[i] == 0: poses[i] = 0
    value = poses[i] + d
    if poses[j] == INF:
        poses[j] = value
    elif poses[j] != value:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
    N, M = [int(x) for x in input().strip().split()]
    if M == 0:
        return "Yes"

    tables = []
    for i in range(M):
        tables.append([int(x) for x in input().strip().split()])
    tables.sort()

    x1, x2, d = tables[0]
    stock = {x1:0}
    for _ in range(2):
        for rows in tables:
            x1, x2, d = rows
            if x1 in stock:
                if x2 in stock:
                    if stock[x2] != stock[x1] + d:
                        return "No"
                else:
                    stock[x2] = stock[x1] + d
    return "Yes"

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

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
P = [None for i in range(N+1)]
Tree = [list() for i in range(N+1)]
for index in range(M):
	L, R, D = (int(i) for i in input().split())
	Tree[L].append((R, D))
	Tree[R].append((L,-D))

for i in range(1,N+1):
	obj = Tree[i]
	if len(obj) != 0:
		if P[i] == None:
			P[i] = 0
		for j, d in obj:
			if P[j] == None:
				P[j] = P[i] + d
			else:
				if P[j] - P[i] != d:
					print("No")
					exit(0)

print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
P = [None for i in range(N+1)]
Tree = [list() for i in range(N+1)]
for index in range(M):
	L, R, D = (int(i) for i in input().split())
	Tree[L].append((R, D))
	Tree[R].append((L,-D))

for i in range(1,N+1):
	obj = Tree[i]
	if len(obj) != 0:
		if P[i] == None:
			P[i] = 0
		for j, d in obj:
			if P[j] == None:
				P[j] = d
			else:
				if P[j] - P[i] != d:
					print("No")
					exit(0)

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, raw_input().split())
if m == 0:
    print "Yes"
    sys.exit()
dic = dict()
lis = list()
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    if l > r:
        t = l
        l = r
        r = t
        lis.append((l, r, -d))
    else:
        lis.append((l, r, d))
lis.sort()
print lis
dic[lis[0][0]] = 0
for l in lis:
    if not l[0] in dic:
        pass
    else:
        if not l[1] in dic:
            dic[l[1]] = dic[l[0]]+l[2]
        else:
            if not dic[l[1]]-dic[l[0]] == l[2]:
                print "No"
                break
else:
    print "Yes"

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, raw_input().split())
if m == 0:
    print "Yes"
    sys.exit()
dic = dict()
lis = list()
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    if l > r:
        t = l
        l = r
        r = t
    lis.append((l, r, d))
lis.sort()
dic[lis[0][0]] = 0
for l in lis:
    if not l[0] in dic:
        pass
    else:
        if not l[1] in dic:
            dic[l[1]] = dic[l[0]]+l[2]
        else:
            if not dic[l[1]]-dic[l[0]] == l[2]:
                print "No"
                break
else:
    print "Yes"

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    if(M == 0):
        print('Yes')
        return
    INF = 1e9
    dist = [INF for i in range(N)]
    L, R, D = map(int, input().split())
    dist[L - 1] = 0
    dist[R - 1] = D
    flag = True
    l = []
    for i in range(M - 1):
        L, R, D = map(int, input().split())
        if(dist[L - 1] != INF and dist[R - 1] != INF):
            if(dist[R - 1] - dist[L - 1] != D):
                flag = False
                break
        elif(dist[L - 1] != INF):
            dist[R - 1] = dist[L - 1] + D
        elif(dist[R - 1] != INF):
            dist[L - 1] = dist[R - 1] + D
        else:
            l.append([L, R, D])
    if(flag == False):
        print('No')
        return
    size = len(l)
    if(size == 0):
        print('Yes')
        return
    
    while(True):
        pre = len(l)
        for i in range(len(l)):
            L, R, D = l[-1]
            l.pop()
            if(dist[L - 1] != INF and dist[R - 1] != INF):
                if(dist[R - 1] - dist[L - 1] != D):
                    flag = False
                    break
            elif(dist[L - 1] != INF):
                dist[R - 1] = dist[L - 1] + D
            elif(dist[R - 1] != INF):
                dist[L - 1] = dist[R - 1] + D
            else:
                l.append([L, R, D])
        if(pre == len(l)):
            break

    if(flag):
        print('Yes')
    else:
        print('No')
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    if(M == 0):
        print('Yes')
        return
    INF = 1e9
    dist = [INF for i in range(N)]
    L, R, D = map(int, input().split())
    dist[L - 1] = 0
    dist[R - 1] = D
    flag = True
    for i in range(M - 1):
        L, R, D = map(int, input().split())
        if(dist[L - 1] != INF and dist[R - 1] != INF):
            if(dist[R - 1] - dist[L - 1] != D):
                flag = False
                break
        elif(dist[L - 1] != INF):
            dist[R - 1] = dist[L - 1] + D
        elif(dist[R - 1] != INF):
            dist[L - 1] = dist[R - 1] + D
    if(flag):
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))

    for i in range(n):
        if x[i]:
            continue
        stack = [i]
        x[i] = 0
        while len(stack) > 0:
            v = stack.pop()
            for u, d in g[v]:
                if not x[u]:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(a, l, r):
    st = [(l, 0)]
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            return d

        if r in a[i]:
            d += a[i][r]
            a[l][r] = d
            st.append((r, d))
            continue

        for k, v in a[i].items():
            d += v
            a[l][k] = d
            st.append((k, d))

    return -1


def main():
    (n, m) = map(int, input().split())
    a = {i:{} for i in range(1, n + 1)}
    for line in sys.stdin:
        (l, r, d) = map(int, line.split())
        pd = dist(a, l, r)
        if pd != -1 and pd != d or dist(a, r, l) != -1:
            print('No')
            sys.exit()
        a[l][r] = d

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(a, l, r):
    st = [(l, 0)]
    found = False
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            found = True
            break

        if a[i][r]:
            if a[i][r] < 0:
                return -2
            d += a[i][r]
            a[l][r] = d
            st.append((r, d))
            continue

        for j in range(len(a[0])):
            if a[i][j]:
                if a[i][j] < 0:
                    return -2
                d += a[i][j]
                a[l][j] = d
                st.append((j, d))
                break

    return d if found == True else -1


def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    a = [[None] * n for _ in range(n)]
    for lrd in lrds:
        (l, r, d) = lrd
        l -= 1
        r -= 1
        pd = dist(a, l, r)
        if pd != -1 and pd != d:
            print('No')
            sys.exit()
        a[l][r] = d
        a[r][l] = -d

    print('Yes')

if __name__ == '__main__':
    main()