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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

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

        if h[i][r]:
            st.append((r, d + h[i][r]))
            continue

        for j in range(len(h[0])):
            if h[i][j]:
                st.append((j, d + h[i][j]))
                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))

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

    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
link = [[] for _ in range(N+1)]
value = [-1 for _ in range(N+1)]

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

searched = set()
q = deque()
for u in range(N+1):
    if u in searched:
        continue
    q.append(u)
    searched.add(u)
    value[u] = 0
    while q:
        x = q.popleft()
        for y, d in link[x]:
            if y not in searched:
                value[y] = value[x] + d
                q.append(y)
                searched.add(y)

for x in range(N+1):
    for y, d in link[x]:
        if value[y] != value[x] + d:
            print('No')
            break
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
d = []
l = []
r = []
branch = dict()
for i in range(n+1):
	branch[i] = []
for i in range(m):
	ltemp,rtemp,dtemp = map(int,input().split())
	branch[ltemp].append((rtemp,dtemp))
	l.append(ltemp)
	r.append(rtemp)
	d.append(dtemp)
x = [None for i in range(n+1)]
arrival = [0 for i in range(n+1)]
check = True



q = []
for i in range(1,n+1):
	if arrival[i] == 0 and check:
		q.append(i)
		if len(branch[q[0]]) == 0:
			arrival[q[0]] = 1
			q.pop(0)
		else:
			x[i] = 0
			while len(q) > 0 and check:
				for k in range(len(branch[q[0]])):
					if x[branch[q[0]][k][0]] == None:
						q.append(branch[q[0]][k][0])
						x[branch[q[0]][k][0]] = x[q[0]] + branch[q[0]][k][1]
					elif x[branch[q[0]][k][0]] != x[q[0]] + branch[q[0]][k][1]:
						check = False
						break
				arrival[q[0]] = 1
				q.pop(0)

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

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
x = [-1 for i in range(n+1)]
xGroup = [0 for i in range(n+1)]
groupNum = 0
result = True
for i in range(m):
    l, r, d = list(map(int, input().split()))
    if xGroup[l] == 0:
        if xGroup[r] == 0:
            groupNum += 1
            x[l] = 0
            xGroup[l] = groupNum
            x[r] = d
            xGroup[r] = groupNum
        else:
            x[l] = x[r] - d
            xGroup[l] = xGroup[r]
    else:
        if xGroup[r] == 0:
            x[r] = x[l] + d
            xGroup[r] = xGroup[l]
        else:
            if x[r] - x[l] != d:
                result = False

groupMin = [1 for i in range(groupNum+1)]
groupMax = [-1 for i in range(groupNum+1)]
for i in range(1, n+1):
    xi = x[i]
    groupi = xGroup[i]
    if xi < groupMin[groupi]:
        groupMin[groupi] = xi
    elif xi > groupMax[groupi]:
        groupMax[groupi] = xi
        
for i in range(1, groupNum+1):
    if groupMax[i]-groupMin[i] > 10000:
        result = False

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

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
x = [-1 for i in range(n+1)]
result = True
for i in range(m):
    l, r, d = list(map(int, input().split()))
    if x[l] == -1:
        if x[r] == -1:
            x[l] = 0
            x[r] = d
        else:
            x[l] = x[r] - d
    else:
        if x[r] == -1:
            x[r] = x[l] + d
        else:
            if x[r] - x[l] != d:
                result = False
if result:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def calc(M):
    posi = {}
    for i in range(M):
        cond = list(map(int, input().split(' ')))  # [Left, right, distance]
        if i == 0:
            posi[cond[0]] = 0
            posi[cond[1]] = cond[2]
        else:
            if cond[0] in posi.keys():
                if cond[1] in posi.keys():
                    if posi[cond[1]] != posi[cond[0]] + cond[2]:
                        return False
                else:
                    posi[cond[1]] = posi[cond[0]] + cond[2]
    return True


if __name__ == '__main__':
    NM = list(map(int, input().split(' ')))
    N = NM[0]
    M = NM[1]

    if calc(M): print('Yes')
    else : print('No')

Submission status: Wrong Answer

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

list = [None for i in range(n)]

result = "Yes"
for i in range(m):
	l, r, d = map(int, input().split())
	
	if (list[l - 1] == None and list[r - 1] == None):
		list[l - 1] = 0
		list[r - 1] = d
	elif(list[l - 1] == None):
		list[l - 1] = list[r - 1] - d
	elif (list[r - 1] == None):
		list[r - 1] = list[l - 1] + d
	else:
		if list[r - 1] != list[l - 1] + d:
			result = "No"
			break

print(result)

Submission status: Wrong Answer

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

list = [None for i in range(n)]

result = "Yes"
for i in range(m):
	l, r, d = map(int, input().split())
	
	if (list[l - 1] == None):
		list[l - 1] = 0
	
	if (list[r - 1] == None):
		list[r - 1] = list[l - 1] + d
	else:
		if list[r - 1] != list[l - 1] + d:
			result = "No"
			break

print(result)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    LRD = tuple(tuple(map(int, input().split())) for _ in [0] * M)

    a = [0] * (N + 1)
    b = []
    bappend = b.append
    for l, r, d in LRD:
        if abs(r - l) == 1:
            if l < r:
                a[r] = a[l] + d
            else:
                a[l] = (a[r] + d) * -1
        else:
            c = (l, r, d)
            bappend(c)

    for l, r, d in b:
        if a[r] - a[l] != d:
            print('No')
            break
    else:
        print('Yes')

main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    LRD = tuple(tuple(map(int, input().split())) for _ in [0] * M)

    a = [0] * (N + 1)
    b = []
    bappend = b.append
    for l, r, d in LRD:
        min_ = min(l, r)
        max_ = max(l, r)
        if max_ - min_ == 1:
            a[max_] = a[min_] + d
        else:
            c = (min_, max_, d)
            bappend(c)

    for l, r, d in b:
        if a[r] - a[l] != d:
            print('No')
            break
    else:
        print('Yes')

main()

Submission status: Wrong Answer

Solution code:
def evaluate_positions(positions, cache, assume_origin_set, unevaluated_positions):
    has_conflict = False
    origin_set = assume_origin_set
    for position_data in positions:
        l, r, d = position_data
        if cache[l] != -1 and cache[r] != -1:
            if cache[r] - cache[l] != d:
                has_conflict = True
                break
        elif cache[l] == -1 and cache[r] != -1:
            cache[l] = cache[r] - d
        elif cache[l] != -1 and cache[r] == -1:
            cache[r] = cache[l] + d
        else:
            if not origin_set:
                cache[l] = 0
                cache[r] = d
            else:
                unevaluated_positions.append(position_data)
    return has_conflict


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    cache = [-1 for _ in range(n + 1)]
    positions = []
    for _ in range(m):
        positions.append(list(map(int, input().split(" "))))
    unevaluated_positions = []

    has_conflict = False
    assume_origin_set = False
    while True:
        has_conflict = evaluate_positions(positions, cache, assume_origin_set, unevaluated_positions)
        if has_conflict:
            break
        if len(unevaluated_positions) == 0:
            break
        if set(positions) == set(unevaluated_positions):
            assume_origin_set = False
        positions = unevaluated_positions
        unevaluated_positions = []

    print("No" if has_conflict else "Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = tuple(map(int, input().split()))
Ls = np.zeros((M,), dtype=int)
Rs = np.zeros((M,), dtype=int)
Ds = np.zeros((M,), dtype=int)

for i in range(M):
    Ls[i], Rs[i], Ds[i] = tuple(map(int, input().split()))

# debug 1 exit()

Ls = Ls - 1
Rs = Rs - 1

adjacency_list = []
for i in range(N):
    adjacency_list.append([])

for i in range(M):
    adjacency_list[Ls[i]].append((Rs[i], Ds[i]))
    adjacency_list[Rs[i]].append((Ls[i], -Ds[i]))

# print(adjacency_list)

# BFSする
visited = np.zeros(N, dtype=bool)
weights = np.zeros(N, dtype=int)

# debug 2 exit()

def DFS(node_index):
    global visited
    global adjacency_list
    global to_be_visited
    global weights
    try:
        candidate = adjacency_list[node_index]
    except:
        pass
        # debug 4 exit()
    for _i, weight in candidate:
        if visited[_i]:
            # print("{}: already visited".format(_i))
            pass
        if not visited[_i]:
            # print("{} found; add to stack".format(_i))
            visited[_i] = True
            weights[_i] = weights[node_index] + weight
            to_be_visited.append(_i)
    if len(to_be_visited) != 0:
        try:
            next_node = to_be_visited.pop()
        except:
            pass
            # exit()
        # DFS(next_node)
    else:
        return 0

pointer = 0
while pointer < N:
    while pointer < N:
        if not visited[pointer]:
            # print("initialized with {}".format(pointer))
            break
        else:
            # print("{} th node already visited".format(pointer))
            pointer += 1
    if not pointer < N:
        break
    to_be_visited = [pointer]
    DFS(pointer)
    pointer += 1

# debug 3 exit()

# print(weights)

for i in range(M):
    # print("given weights: {}, estimated weights: {}".format(Ds[i],weights[Rs[i]]-weights[Ls[i]]))
    if weights[Rs[i]] - weights[Ls[i]] == Ds[i]:
        # print("passed {} th condition".format(i))
        pass
    else:
        # print("failed {} th condition".format(i))
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = tuple(map(int, input().split()))
Ls = np.zeros((M,), dtype=int)
Rs = np.zeros((M,), dtype=int)
Ds = np.zeros((M,), dtype=int)

for i in range(M):
    Ls[i], Rs[i], Ds[i] = tuple(map(int, input().split()))

# debug 1 exit()

Ls = Ls - 1
Rs = Rs - 1

adjacency_list = []
for i in range(N):
    adjacency_list.append([])

for i in range(M):
    adjacency_list[Ls[i]].append((Rs[i], Ds[i]))
    adjacency_list[Rs[i]].append((Ls[i], -Ds[i]))

# print(adjacency_list)

# BFSする
visited = np.zeros(N, dtype=bool)
weights = np.zeros(N, dtype=int)

exit()

def DFS(node_index):
    global visited
    global adjacency_list
    global to_be_visited
    global weights
    candidate = adjacency_list[node_index]
    for _i, weight in candidate:
        if visited[_i]:
            # print("{}: already visited".format(_i))
            pass
        if not visited[_i]:
            # print("{} found; add to stack".format(_i))
            visited[_i] = True
            weights[_i] = weights[node_index] + weight
            to_be_visited.append(_i)
    if len(to_be_visited) != 0:
        next_node = to_be_visited.pop()
        DFS(next_node)
    else:
        return 0

pointer = 0
while pointer < N:
    while pointer < N:
        if not visited[pointer]:
            # print("initialized with {}".format(pointer))
            break
        else:
            # print("{} th node already visited".format(pointer))
            pointer += 1
    if not pointer < N:
        break
    to_be_visited = [pointer]
    DFS(pointer)
    pointer += 1

# print(weights)

for i in range(M):
    # print("given weights: {}, estimated weights: {}".format(Ds[i],weights[Rs[i]]-weights[Ls[i]]))
    if weights[Rs[i]] - weights[Ls[i]] == Ds[i]:
        # print("passed {} th condition".format(i))
        pass
    else:
        # print("failed {} th condition".format(i))
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = tuple(map(int, input().split()))
Ls = np.zeros((M,), dtype=int)
Rs = np.zeros((M,), dtype=int)
Ds = np.zeros((M,), dtype=int)

for i in range(M):
    Ls[i], Rs[i], Ds[i] = tuple(map(int, input().split()))

exit()

Ls = Ls - 1
Rs = Rs - 1

adjacency_list = []
for i in range(N):
    adjacency_list.append([])

for i in range(M):
    adjacency_list[Ls[i]].append((Rs[i], Ds[i]))
    adjacency_list[Rs[i]].append((Ls[i], -Ds[i]))

# print(adjacency_list)

# BFSする
visited = np.zeros(N, dtype=bool)
weights = np.zeros(N, dtype=int)


def DFS(node_index):
    global visited
    global adjacency_list
    global to_be_visited
    global weights
    candidate = adjacency_list[node_index]
    for _i, weight in candidate:
        if visited[_i]:
            # print("{}: already visited".format(_i))
            pass
        if not visited[_i]:
            # print("{} found; add to stack".format(_i))
            visited[_i] = True
            weights[_i] = weights[node_index] + weight
            to_be_visited.append(_i)
    if len(to_be_visited) != 0:
        next_node = to_be_visited.pop()
        DFS(next_node)
    else:
        return 0

pointer = 0
while pointer < N:
    while pointer < N:
        if not visited[pointer]:
            # print("initialized with {}".format(pointer))
            break
        else:
            # print("{} th node already visited".format(pointer))
            pointer += 1
    if not pointer < N:
        break
    to_be_visited = [pointer]
    DFS(pointer)
    pointer += 1

# print(weights)

for i in range(M):
    # print("given weights: {}, estimated weights: {}".format(Ds[i],weights[Rs[i]]-weights[Ls[i]]))
    if weights[Rs[i]] - weights[Ls[i]] == Ds[i]:
        # print("passed {} th condition".format(i))
        pass
    else:
        # print("failed {} th condition".format(i))
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
def root(x):
    if x == parent[x]:
        return x
    y = root(parent[x])
    dist[x] += dist[parent[x]]
    parent[x] = y
    return y
def unite(x, y, d):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
        dist[py] = dist[x] - d
    else:
        parent[px] = py
        dist[px] = dist[y] + d

n, m = map(int, input().split())
*parent, = range(n)
dist = [0]*n
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1; r -= 1
    if root(l) == root(r):
        if dist[l] - dist[r] != d:
            print("No")
            exit(0)
    else:
        unite(l, r, d)
print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, raw_input().split())
graph = {_: set() for _ in xrange(n + 1)}
in_deg, dist = [0] * (n + 1), [-1] * (n + 1)
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    graph[l].add((r, d))
    in_deg[r] += 1
que = deque([i for i in xrange(n + 1) if not in_deg[i]])
cst = 1
while que:
    stp = que.popleft()  # start_point
    if in_deg[stp] < 0:
        in_deg[stp] = cst
    for v, d in graph[stp]:
        if dist[v] < 0:
            dist[v] = dist[stp] + d
        else:
            if dist[v] != dist[stp] + d:
                print 'No'
                exit()
        in_deg[v] -= 1
        if not in_deg[v]:
            que.append(v)
print 'Yes' if any(in_deg) else 'No'

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(200000)

def reachable(td, origL, l, r, d):
    if not(l in td):
        return (False, d)
    vd = td[l]

    if origL in vd:
        return (False, d)

    if r in vd:
        return (True, d + vd[r])

    for er, ed in vd.iteritems():
        rb, rd = reachable(td, origL, er, r, d + ed)
        if rb:
            return (True, rd)
        
    return (False, d)

n, m = [int(i) for i in raw_input().split()]
tl = list()
for i in range(m):
    l = [int(i) for i in raw_input().split()]
    tl.append(l)
# print n, m
# print tl

consistent = 'Yes'
td = dict()
for t in tl:
    l, r, d = t
    
    found, fd = reachable(td, r, r, l, 0)
    if found:
        consistent = 'No'
        break
    
    found, fd = reachable(td, l, l, r, 0)
    if found:
        if fd != d:
            consistent = 'No'
            break
        # else:
        #     td[l][r] = d
    else:
        if not (l in td):
            td[l] = dict()
        td[l][r] = d

sys.stdout.write('%s\n' % consistent)
sys.stdout.flush()

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split(" ")]

from collections import defaultdict
pair_distances = defaultdict(lambda : defaultdict(list))
for i in range(m):
    r, l, d = [int(x) for x in input().split(" ")]
    pair_distances[r][l].append(d)
    pair_distances[l][r].append(d * -1)

simple_missmatch = False
for r, othersides in pair_distances.items():
    for l, distances in othersides.items():
        if len(distances) > 1:
            max_distance, min_distance = max(distances), min(distances)
            if max_distance != min_distance:
                simple_missmatch = True
                break
    if simple_missmatch:
        break

if simple_missmatch:
    print("NO")
else:
    passed = {}
    positions = defaultdict(int)
    persons = list(pair_distances.keys())
    position_missmatch = False
    for r in persons:
        
        if r in passed:
            continue
        
        positions[r] = 0
        remains = [(r)]
        passed[r] = 1
        while remains:
            p = remains.pop(0)
            pos = positions[p]
            
            for l in pair_distances[p]:
                if not l in positions:
                    positions[l] = pos + pair_distances[p][l][0]
                else:
                    if positions[l] != pos + pair_distances[p][l][0]:
                        position_missmatch = True
                        break
                if not l in passed:
                    remains.append(l)
                    passed[l] = 1
            if position_missmatch:
                break
        if position_missmatch:
            break
    if position_missmatch:
        print("NO")
    else:
        print("YES")

Submission status: Wrong Answer

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

graph = {}
if not m:
    print("Yes")
    __import__("sys").exit()


for i in range(m):
    a, b, c = map(int, input().split())
    a_value = graph.get(a)
    if a_value is None:
        a_value = []
        graph[a] = a_value
    a_value.append((b, c))

    b_value = graph.get(b)
    if b_value is None:
        b_value = []
        graph[b] = b_value
    b_value.append((a, -c))


keys = list(graph.keys())
visited = {}
for key in keys:
    visited[key] = False

start = keys[0]

queue = [(0, graph[start])]
while queue:
    cost, next_targets = queue.pop()
    for next_node, next_cost in next_targets:
        vcost = visited[next_node]
        if vcost == False:
            ncost = cost + next_cost
            visited[next_node] = ncost
            queue.append((ncost, graph[next_node]))
        else:
            if vcost != cost + next_cost:
                print("No")
                __import__("sys").exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys                                                   
l1 = list(map(int, input().split()))                         
N = l1[0]                                                    
M = l1[1]                                                    
                                                             
dat = []                                                     
                                                             
#per_dis = [[ 0 for n in range(N+1)] for n in range(N+1)]    
                                                             
per_dis = [ [] for n in range(N+1)]                          
                                                             
for n in range(M):                                           
    x = list(map(int, input().split()))                      
    dat.append(x)                                            
                                                             
def bfs(start, goal):                                        
    visited = []                                             
    unvisited = [(start, 0)]                                 
    while unvisited:                                         
        print(unvisited)                                     
        now = unvisited[0]                                   
        unvisited = unvisited[1:]                            
        for next in per_dis[now[0]]:                         
            if next[0] not in visited:                       
                if next[0] == goal:                          
                    return now[1] + next[1]                  
                unvisited.append((next[0], now[1] + next[1]))
                visited.append(next[0])                      
    return None                                              
                                                             
for x in dat:                                                
    if None == bfs(x[0], x[1]):                              
        per_dis[x[0]].append((x[1],x[2]))                    
        per_dis[x[1]].append((x[0],-x[2]))                   
    elif  x[2] != bfs(x[0], x[1]):                           
        print("No")                                          
        sys.exit(0)                                          
                                                             
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys                                                    
l1 = list(map(int, input().split()))                          
N = l1[0]                                                     
M = l1[1]                                                     
                                                              
dat = []                                                      
                                                              
#per_dis = [[ 0 for n in range(N+1)] for n in range(N+1)]     
                                                              
per_dis = [ [] for n in range(N+1)]                           
                                                              
for n in range(M):                                            
    x = list(map(int, input().split()))                       
    dat.append(x)                                             
                                                              
def bfs(start, goal):                                         
    visited = []                                              
    unvisited = [(start, 0)]                                  
    while unvisited:                                          
        now = unvisited[0]                                    
        unvisited = unvisited[1:]                             
        for next in per_dis[now[0]]:                          
            if next[0] not in visited:                        
                if next[0] == goal:                           
                    return now[1] + next[1]                   
                unvisited.append((next[0], now[1] + next[1])) 
                visited.append(next[0])                       
    return None                                               
                                                              
for x in dat:                                                 
    if None == bfs(x[0], x[1]):                               
        per_dis[x[0]].append((x[1],x[2]))                     
        per_dis[x[1]].append((x[0],-x[2]))                    
    elif  x[2] != bfs(x[0], x[1]):                            
        print("No")                                           
        sys.exit(0)

Submission status: Wrong Answer

Solution code:
import sys


N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    k, l, m = map(int, input().split())
    L.append(k)
    R.append(l)
    D.append(m)

graph = [[] for i in range(N)]

for i, j, k in zip(L, R, D):
    graph[i-1].append((j-1, k))
    # graph[j-1].append((i-1, -k))

DP = [None] * N
VISITED = [False] * N
for i in range(N):
    if not VISITED[i]:
        queue = [i]
        DP[i] = 0
        while queue:
            label = queue.pop(0)
            if not VISITED[label]:
                for j, k in graph[label]:
                    DP[j] = DP[label] + k
                    queue.append(j)
                VISITED[label] = True

for i, j, k in zip(L, R, D):
    if DP[j-1] - DP[i-1] != k:
        print('No')
        sys.exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys


N, M = map(int, input().split())
L = []
R = []
D = []
for i in range(M):
    k, l, m = map(int, input().split())
    L.append(k)
    R.append(l)
    D.append(m)

graph = [[] for i in range(N)]

for i, j, k in zip(L, R, D):
    graph[i-1].append((j-1, k))
    graph[j-1].append((i-1, -k))

DP = [None] * N
VISITED = [False] * N
for i in range(N):
    if not VISITED[i]:
        queue = [i]
        DP[i] = 0
        while queue:
            label = queue.pop(0)
            if not VISITED[label]:
                for j, k in graph[label]:
                    DP[i] = DP[label] + j
                    queue.append(i)
                VISITED[label] = True

for i, j, k in zip(L, R, D):
    if DP[j-1] - DP[i-1] != k:
        print('No')
        sys.exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
def work():
    
    proceed=1

    while proceed>0:
       proceed=0
       for i in range(m):
          if (pos[d[i][0]]<>-1):
             if (pos[d[i][1]]<>-1):
                if (pos[d[i][1]]<>pos[d[i][0]]+d[i][2]) :
                   return "NG"
             else:
                pos[d[i][1]]=pos[d[i][0]]+d[i][2]
                proceed=proceed+1

    return "YES"
    

def judgeset():
    
    w=True

    for i in range(m):
        if pos[d[i][0]]==-1 :
            pos[d[i][0]]=0
            pos[d[i][1]]=d[i][2]
            w=False
            break
    return w
        
    



n,m = map(int, raw_input().split())
d=[]
for i in range(m):
   w = map(int, raw_input().split())
   d.append(w)

pos=[-1]*(n+1)


while True:
    if judgeset()==True :
        print "Yes"
        break
    if work()=="NG" :
        print "No"
        break

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}
test={}
start=0
for i in range(M):
	L,R,D=map(int,raw_input().split())
	if i==0:start=L
	nl[L].append(R)
	nl[R].append(L)
	cost[(L,R)]=D
	cost[(R,L)]=-D

d=[ -1 for i in range(N+1) ]
V=[ 0 for i in range(N+1) ]

q = deque([]) 
V[start]=1
d[start]=0
q.append(start)

while len(q)!=0:
	v=q.pop()
	for i in nl[v]:
		if V[i]!=1:
			V[i]=1
			q.append(i)
			d[i]=d[v]+cost[(v,i)]



for i,j in cost.items():
	x1=i[0]
	x2=i[1]
	if d[x2]-d[x1]==j:
		continue
	else:
		print "No"
		quit()
else:
	print "Yes"

Submission status: Wrong Answer

Solution code:
x =[int(i) for i in input().split()]
N = x[0]
M = x[1]
A = [[int(j) for j in input().split()] for i in range(M)]

X = [0 for i in range(N)]

for cond in A:
    X[cond[1]-1] = X[cond[0]-1] + cond[2]

state = True
for cond in A:
    if X[cond[1]-1] != X[cond[0]-1] + cond[2]:
        state = False

if max(X) - min(X) >= 10**9:
    state = False

if state == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
x =[int(i) for i in input().split()]
N = x[0]
M = x[1]
A = [[int(j) for j in input().split()] for i in range(M)]

X = [0 for i in range(N)]

for cond in A:
    X[cond[1]-1] = X[cond[0]-1] + cond[2]

state = 0
for cond in A:
    if X[cond[1]-1] != X[cond[0]-1] + cond[2]:
        state +=1

if state == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
NOT_VISIT = -999999
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))

visited = [NOT_VISIT for i in range(N)]

def dfs(start):
	global graph, visited

	if visited[start] != NOT_VISIT:
		return True

	stack = [start]
	visited[start] = 0
	while stack:
		label = stack.pop()
		for nextnode, distance in graph[label]:
			if visited[nextnode] == NOT_VISIT:
				stack.append(nextnode)
				visited[nextnode] = visited[label] + distance
			elif visited[nextnode] != visited[label] + distance:
				return False
	return True

res = True
for i in range(N):
	res &= dfs(i)

print("Yes" if res == True else "No")

Submission status: Wrong Answer

Solution code:
import sys 

temp=input().split(" ")
n=int(temp[0])
m=int(temp[1])
# p=[[-1 for i in range(n)] for j in range(n)]
p=[]
dis=[-1]*(n+5000)
for i in range(m):
    temp=input()
    temp=list(map(int,temp.split(" ")))
    p.append(temp)
if m!=0:
   
    for temp in p:
        x=int(temp[0])
        y=int(temp[1])    
        d=int(temp[2])
        if dis[y]!=dis[x]+d:
            # print (x)
            # print (y)
            # print (d)
            print("No")
            sys.exit()
        if dis[x]==-1 and dis[y]==-1: #完全な新情報なら
            dis[x]=0
            dis[y]=d
        elif dis[x]==-1: #xだけ不明なら
            dis[x]=dis[y]-d
        elif dis[y]==-1:
            dis[y]=dis[x]+d
        
print("Yes")