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: Time Limit Exceeded

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)                                                                           
                                                                                            
                                                                                            
for x in dat:                                                                               
    if per_dis[x[0]][x[1]] == 0 and per_dis[x[1]][x[0]] == 0:                               
        per_dis[x[0]][x[1]] = x[2]                                                          
        per_dis[x[1]][x[0]] = -x[2]                                                         
        for i in range(1,N):                                                                
            for j in range(i+1,N):                                                          
                if per_dis[i][j] != 0 and per_dis[i+1][j+1] != 0 and per_dis[i][j+1] == 0:  
                    per_dis[i][j+1] = per_dis[i][j] + per_dis[i+1][j+1]                     
                    per_dis[j+1][i] = -per_dis[i][j+1]                                      
                elif per_dis[i][j] == 0 and per_dis[i+1][j+1] != 0 and per_dis[i][j+1] != 0:
                    per_dis[i][j] = per_dis[i][j+1] - per_dis[i+1][j+1]                     
                    per_dis[j][i] = -per_dis[i][j]                                          
                elif per_dis[i][j] != 0 and per_dis[i+1][j+1] == 0 and per_dis[i][j+1] != 0:
                    per_dis[i+1][j+1] = per_dis[i][j+1] - per_dis[i][j]                     
                    per_dis[j+1][i+1] = -per_dis[i+1][j+1]                                  
    else:                                                                                   
        if abs(per_dis[x[0]][x[1]]) != x[2]:                                                
            print("No")                                                                     
            sys.exit(0)                                                                     
                                                                                            
print("Yes")

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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
unvisited = set(range(N))
while unvisited:
    start = list(unvisited)[0]
    queue = [start]
    DP[start] = 0
    while queue:
        label = queue.pop(0)
        if label in unvisited:
            for i, j in graph[label]:
                DP[i] = DP[label] + j
                queue.append(i)
            unvisited.remove(label)

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: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}

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=[ None for i in range(N+1) ]
V=[ 0 for i in range(N+1) ]
V2=[]

def dfs(start):
	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
				V2.append((v,i))
				q.append(i)
				d[i]=d[v]+cost[(v,i)]
			
			if (v,i) not in V2:
				if d[v]-d[i]!=cost[(i,v)]:
					print "No"
					quit()

for i in range(1,N+1):
	if V[i]==0:
		dfs(i)
else:
	print "Yes"

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}
test={}

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
	test[(L,R)]=D


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

def dfs(start):
	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 in range(1,N+1):
	if d[i]==-1:
		dfs(i)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}
test={}

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
	test[(L,R)]=D


d=defaultdict(lambda: -1)

def dfs(start):
	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 test.items():
	x1=i[0]
	x2=i[1]

	if d[x1]==-1:
		dfs(x1)
	if d[x2]-d[x1]==j:
		continue
	else:
		print "No"
		quit()
else:
	print "Yes"

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}
test={}

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
	test[(L,R)]=D


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

def dfs(start):
	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 test.items():
	x1=i[0]
	x2=i[1]

	if d[x1]==-1:
		dfs(x1)
	if d[x2]-d[x1]==j:
		continue
	else:
		print "No"
		quit()
else:
	print "Yes"

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}
test={}

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

def dfs(start):
	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[x1]==-1:
		dfs(x1)
	if d[x2]-d[x1]==j:
		continue
	else:
		print "No"
		quit()
else:
	print "Yes"

Submission status: Time Limit Exceeded

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)]                                    
                                                                                            
for n in range(M):                                                                          
    x = list(map(int, input().split()))                                                     
    dat.append(x)                                                                           
                                                                                            
for x in dat:                                                                               
    if per_dis[x[0]][x[1]] == 0 and per_dis[x[0]][x[1]] == 0:                               
        per_dis[x[0]][x[1]] = x[2]                                                          
        per_dis[x[1]][x[0]] = -x[2]                                                         
        for i in range(1,N):                                                                
            for j in range(i+1,N):                                                          
                if per_dis[i][j] != 0 and per_dis[i+1][j+1] != 0 and per_dis[i][j+1] == 0:  
                    per_dis[i][j+1] = per_dis[i][j] + per_dis[i+1][j+1]                     
                    per_dis[j+1][i] = -per_dis[i][j+1]                                      
                elif per_dis[i][j] == 0 and per_dis[i+1][j+1] != 0 and per_dis[i][j+1] != 0:
                    per_dis[i][j] = per_dis[i][j+1] - per_dis[i+1][j+1]                     
                    per_dis[j][i] = -per_dis[i][j]                                          
                elif per_dis[i][j] != 0 and per_dis[i+1][j+1] == 0 and per_dis[i][j+1] != 0:
                    per_dis[i+1][j+1] = per_dis[i][j+1] - per_dis[i][j]                     
                    per_dis[j+1][i+1] = -per_dis[i+1][j+1]                                  
    else:                                                                                   
        if abs(per_dis[x[0]][x[1]]) != x[2]:                                                
            print("No")                                                                     
            sys.exit(0)                                                                     
                                                                                            
                                                                                            
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def __logging(visited, rest=[]):
    if rest:
        print(' visited:'+str(visited)+'\n'+
              '    rest:'+str(rest)+'\n')
    else:
        print(' visited:'+str(visited))


def dfs(graph, start, visited):
    if visited[start] != -99999:
        return True
    
    stack = [(start, 0)]
    distance = []
    flag = True
    while stack:
        temp = stack.pop(0)
        label = temp[0]
        dis = temp[1]
        if visited[label] == -99999:
            tmp = graph[label]
            tmp = list(map(lambda x: (x[0], x[1] + dis), tmp))
            stack = tmp + stack
            visited[label] = dis
        else:
            if flag and dis != visited[label]:
                flag = False
        #__logging(visited, stack)
    return flag

N, M = (int(i) for i in input().split())  

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

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


visited = [-99999 for i in range(N+1)]

flag = True
for i in range(N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

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

Submission status: Time Limit Exceeded

Solution code:
def __logging(visited, rest=[]):
    if rest:
        print(' visited:'+str(visited)+'\n'+
              '    rest:'+str(rest)+'\n')
    else:
        print(' visited:'+str(visited))


def dfs(graph, start, visited):
    if start in visited:
        return True
    
    stack = [(start, 0)]
    distance = []
    flag = True
    while stack:
        temp = stack.pop(0)
        label = temp[0]
        dis = temp[1]
        if label not in visited:
            tmp = graph.get(label, [])
            tmp = list(map(lambda x: (x[0], x[1] + dis), tmp))
            stack = tmp + stack
            visited[label] = dis
        else:
            if flag and dis != visited[label]:
                flag = False
        #__logging(visited, stack)
    return flag

N, M = (int(i) for i in input().split())  

m_list = []
graph = {}

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    if L not in graph:
        graph[L] = [(R, D)]
        m_list.append(L)
    else:
        graph[L].append((R, D))
    if R not in graph:
        graph[R] = [(L, -1 * D)]
        m_list.append(R)
    else:
        graph[R].append((L, -1 * D))

visited = {}
flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

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

Submission status: Time Limit Exceeded

Solution code:
def __logging(visited, rest=[]):
    if rest:
        print(' visited:'+str(visited)+'\n'+
              '    rest:'+str(rest)+'\n')
    else:
        print(' visited:'+str(visited))


def dfs(graph, start, visited):
    if start in visited:
        return True
    
    stack = [(start, 0)]
    visited = {}
    distance = []
    flag = True
    while stack:
        temp = stack.pop(0)
        label = temp[0]
        dis = temp[1]
        if label not in visited:
            tmp = graph.get(label, [])
            tmp = list(map(lambda x: (x[0], x[1] + dis), tmp))
            stack = tmp + stack
            visited[label] = dis
        else:
            if flag and dis != visited[label]:
                flag = False
        #__logging(visited, stack)
    return flag

N, M = (int(i) for i in input().split())  

m_list = []
graph = {}

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    if L not in graph:
        graph[L] = [(R, D)]
        m_list.append(L)
    else:
        graph[L].append((R, D))
    if R not in graph:
        graph[R] = [(L, -1 * D)]
        m_list.append(R)
    else:
        graph[R].append((L, -1 * D))

visited = {}
flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

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

Submission status: Time Limit Exceeded

Solution code:

def __logging(visited, rest=[]):
    if rest:
        print(' visited:'+str(visited)+'\n'+
              '    rest:'+str(rest)+'\n')
    else:
        print(' visited:'+str(visited))


def dfs(graph, start):
    stack = [(start, 0)]
    visited = {}
    visited_list = []
    distance = []
    while stack:
        temp = stack.pop(0)
        label = temp[0]
        dis = temp[1]
        if label not in visited:
            tmp = graph.get(label, [])
            tmp = list(map(lambda x: (x[0], x[1] + dis), tmp))
            stack = tmp + stack
            visited[label] = dis
            visited_list.append(label)
        else:
            if dis != visited[label]:
                return False, visited_list
        #__logging(visited, stack)
    return True, visited_list

N, M = (int(i) for i in input().split())  

m_list = range(N)
graph = {}

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    if L not in graph:
        graph[L] = [(R, D)]
    else:
        graph[L].append((R, D))
    if R not in graph:
        graph[R] = [(L, -1 * D)]
    else:
        graph[R].append((L, -1 * D))

flag = True
while m_list != []:
    ans, visited_list = dfs(graph, m_list[0])
    if not ans:
        flag = False
        break
    m_list = list(set(visited_list) ^ set(m_list))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = [int(a) for a in input().split()]
LRD_ = []
for i in range(M):
    LRD_.append([int(a) for a in input().split()])

LRD = sorted(LRD_)

if M == 0 or N == 1:
    print("Yes")
    exit(0)

len_na = 0

while True:
    not_appear = []
    if len_na == len(not_appear):
        place = np.ones(2 * N + 1) * -1
        l,r,d = LRD.pop(0)
        place[l+N] = 0
        place[r+N] = place[l+N] + d
    len_na = len(not_appear)
    for l, r, d in LRD:
        if place[l+N] == -1 and place[r+N] == -1:
            not_appear.append((l, r, d))
            continue
        if place[r+N] == -1:
            place[r+N] = place[l+N] + d
            continue
        if place[l+N] == -1:
            place[l+N] = place[r+N] - d
            continue
        if place[r+N] != place[l+N] + d:
            print("No")
            exit(0)
    LRD = not_appear
    if LRD == []:
        break

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = [int(a) for a in input().split()]
LRD_ = []
for i in range(M):
    LRD_.append([int(a) for a in input().split()])

LRD = sorted(LRD_)

if M == 0 or N == 1:
    print("Yes")
    exit(0)

len_na = 0

while True:
    not_appear = []
    if len_na == len(not_appear):
        place = np.ones(2 * N + 1) * -1
        l,r,d = LRD.pop(0)
        place[l+N] = 0
        place[r+N] = place[l+N] + d
        len_na = len(not_appear)
    for l, r, d in LRD:
        if place[l+N] == -1 and place[r+N] == -1:
            not_appear.append((l, r, d))
            continue
        if place[r+N] == -1:
            place[r+N] = place[l+N] + d
            continue
        if place[l+N] == -1:
            place[l+N] = place[r+N] - d
            continue
        if place[r+N] != place[l+N] + d:
            print("No")
            exit(0)
    LRD = not_appear
    if LRD == []:
        break

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = []
r = []
d = []

data = []
data2 = []
x = []
number = []
Min = 10**9
Max = 0
for i in range(m):
  lt, rt, dt = map(int, input().split())
  data.append((lt, rt, dt))
  temp = max(lt, rt)
  number.append(lt)
  if Min > lt:
    Min = lt
  if temp > Max:
    Max = temp
  while len(x) < Max:
    x.append(0)

number = set(number)


length = len(data)
while length > 0:
  temp = 10**9
  for i in reversed(range(length)):
    if data[i][0] == Min:
      x[data[i][1]-1] = x[Min-1] + data[i][2]
      data2.append(data.pop(i))
  if len(number) > 0:
    Min = number.pop()
  else:
    break
  length = len(data)

for d in data2:
  if x[d[1]-1] - x[d[0]-1] != d[2]:
    print("No")
    exit(0)
print("Yes")

Submission status: Time Limit Exceeded

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

for i in range(0, M):
    L,R,D = map(int, input().split())
    if L < R :
        Restriction.append((L, R, D))
    else:
        Restriction.append((R, L, -D))

if not Restriction:
    print("Yes")
    exit()

Restriction.sort()
while Restriction:
    candidate = {min([ rel[0] for rel in Restriction]):0}
    for rel in Restriction.copy():
        Restriction.remove(rel)
        if rel[0] not in candidate and rel[1] not in candidate:
            Restriction.append(rel)
        elif rel[0] in candidate and rel[1] in candidate:
            if candidate[rel[1]] - candidate[rel[0]] != rel[2]:
                print("No")
                exit()
        elif rel[0] in candidate:
            candidate[rel[1]] = candidate[rel[0]] + rel[2]
        elif rel[1] in candidate:
            candidate[rel[0]] = candidate[rel[1]] - rel[2]
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, sys.stdin.readline().split())
dat = [ list(map(int, sys.stdin.readline().split())) for _ in range(m) ]
dat.sort()
pos = [ None for _ in range(n) ]
if m == 0:
    print("Yes")
    quit()
l, r, d = dat.pop()
pos[l-1] = 0
pos[r-1] = d
while dat:
    ins = False
    for l, r, d in dat:
        if pos[l-1] is not None or pos[r-1] is not None:
            ins = True
        if pos[l-1] is not None and pos[r-1] is not None:
            dat.remove([l, r, d])
            if pos[r-1] - pos[l-1] != d:
                print("No")
                quit()
        elif pos[l-1] is not None:
            dat.remove([l, r, d])
            pos[r-1] = pos[l-1] + d
        elif pos[r-1] is not None:
            dat.remove([l, r, d])
            pos[l-1] = pos[r-1] - d
    if not ins:
        l, r, d = dat.pop()
        pos[l-1] = 0
        pos[r-1] = d
print("Yes")

Submission status: Time Limit Exceeded

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

for i in range(0, M):
    L,R,D = map(int, input().split())
    if L < R :
        Restriction.append((L, R, D))
    else:
        Restriction.append((R, L, -D))

while Restriction:
    tmp = Restriction.copy()
    tmp.sort()
    Restriction.clear()
    candidate = {min([ rel[0] for rel in tmp]):0}
    for rel in tmp:
        if rel[0] not in candidate and rel[1] not in candidate:
            Restriction.append(rel)
        elif rel[0] in candidate and rel[1] in candidate:
            if candidate[rel[1]] - candidate[rel[0]] != rel[2]:
                print("No")
                exit()
        elif rel[0] in candidate:
            candidate[rel[1]] = candidate[rel[0]] + rel[2]
        elif rel[1] in candidate:
            candidate[rel[0]] = candidate[rel[1]] - rel[2]
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import Queue
n, m = map(int, sys.stdin.readline().split())
q = Queue()
for _ in range(m):
    q.put(list(map(int, sys.stdin.readline().split())))
pos = [ None for _ in range(n) ]
if m == 0:
    print("Yes")
    quit()
l, r, d = q.get()
pos[l-1] = 0
pos[r-1] = d
while not q.empty():
    l, r, d = q.get()
    if pos[l-1] is not None and pos[r-1] is not None:
        if pos[r-1] - pos[l-1] != d:
            print("No")
            quit()
    elif pos[l-1] is not None:
        pos[r-1] = pos[l-1] + d
    elif pos[r-1] is not None:
        pos[l-1] = pos[r-1] - d
    else:
        q.put([l, r, d])
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
X=[]
for _ in range(M):
    L,R,D=map(int,input().split())
    j = k = None
    for i in range(len(X)):
        if L in X[i]:
            j = i
        if R in X[i]:
            k = i
    if j is None and k is None:
        X.append({L:0, R:D})
    elif j is not None and k is None:
        X[j][R] = X[j][L] + D
    elif j is None:
        X[k][L] = X[k][R] - D
    elif j != k:
        X[j].update(dict([(i,X[k][i]-X[k][R]+X[j][L]+D) for i in X[k].keys()]))
        del X[k]
    elif X[j][R] - X[k][L] != D:
        print("No")
        exit()
print("Yes")

Submission status: Time Limit Exceeded

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

    n = [[-1 for _ in [0] * (N + 1)] for _ in [0] * (N + 1)]
    for l, r, d in LRD:
        n[l][r] = d
        n[r][l] = d

    for l, r, d in LRD:
        dist = 0
        if abs(l - r) > 1:
            for i in range(min(l, r), max(l, r)):
                dist += n[i][i+1]
            if dist != n[l][r]:
                print('No')
                return
    print('Yes')

main()

Submission status: Time Limit Exceeded

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

infos = []
man_info = []
array = [ [-1 for i in range(N+1)] for i in range(N+1)]

#print array

for i in range(M):
    info = map(int, raw_input().split())
    infos.append(info)
#    print info[0], info[1]
    man_info.append(info[0])
    man_info.append(info[1])
    array[info[0]][info[1]] = info[2]
    array[info[1]][info[0]] = info[2]

people = list(set(man_info))

#print array
#print people

flag = True

for info in infos:
    man1 = info[0]
    man2 = info[1]
    distance = info[2]
    for tmp in people:
        if (array[man1][tmp] == -1) or (array[tmp][man2] == -1):
            pass
        else:
            if (array[man1][tmp] + array[tmp][man2]) == distance:
                pass
            elif (array[man1][tmp] - array[tmp][man2]) == distance:
                pass
            elif (array[man2][tmp] - array[tmp][man1]) == distance:
                pass
            else:
                flag = False
                break

    if flag == False:
        break
    else:
        pass


if flag == True:
    print 'Yes'
else:
    print 'No'

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
    
    def find_root(self, x):
        while 0 <= self.table[x]:
            x = self.table[x]
        return x

    def union(self, x, y):
        r1 = self.find_root(x)
        r2 = self.find_root(y)
        if r1 != r2:
            self.table[r2] = r1
    
    def __repr__(self):
        return repr(self.table)

def check(root, group, l, r, d):
    seen = set()
    table = {}
    table[root] = 0
    seen.add(root)
    while len(seen) != len(group):
        for li, ri, di in zip(l, r, d):
            if (li not in seen) and (ri not in seen):
                continue
            if (li in seen) and (ri in seen):
                if table[li]+di != table[ri]:
                    return False
            elif li in seen:
                table[ri] = table[li] + di
                seen.add(ri)
            elif ri in seen:
                table[li] = table[ri] - di
                seen.add(li)
    return True

def main():
    n, m = map(int, input().split())
    l, r, d = [], [], []
    seen = set()
    tree = UnionFindTree(n+1)
    for i in range(m):
        li, ri, di = map(int, input().split())
        l.append(li)
        r.append(ri)
        d.append(di)
        seen.add(li)
        seen.add(ri)
        tree.union(li, ri)
    
    groups = {}
    for s in seen:
        root = tree.find_root(s)
        if root not in groups:
            groups[root] = set()
        groups[root].add(s)
    
    for root in groups:
        if not check(root, groups[root], l, r, d):
            print('No')
            return
    print('Yes')

main()

Submission status: Time Limit Exceeded

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

L=[]
R=[]
D=[]
for i in range(M):
    l,r,d=map(int, input().split())
    L.append(max(l,r))
    R.append(min(l,r))
    D.append(d)

T=[]
X=[0]*N
for i in range(M):
    if X[L[i]-1]==0:
        X[L[i]-1]=sum(X[0:R[i]])+D[i]
    elif X[L[i]-1]!=0 and X[L[i]-1]-X[R[i]-1]!=D[i]:
        T.append(i)

t=0
for i in T:
    if X[L[i]-1]!=0 and X[L[i]-1]-X[R[i]-1]!=D[i]:
        t=1

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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python
# coding: utf-8


def slove(n, m, dis):
    if m == 0:
        return "Yes"

    mat = [[0 for i in range(n+1)] for j in range(n+1)]
    dict = {}

    for i in range(m):
        l = int(dis[i][0])
        r = int(dis[i][1])
        mat[l][r] = int(dis[i][2])
        if l in dict and r in dict:
            tmp = mat[l][dict[l]] + mat[dict[r]][r]
            if mat[l][r] != tmp:
                return "No"
        dict[l] = r
        dict[r] = l

    return "Yes"


if __name__ == "__main__":
    nm = input().split(" ")
    n = int(nm[0])
    m = int(nm[1])

    dis = []
    for _ in range(m):
        dis.append(input().split(" "))

    print(slove(n, m, dis))