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
#read = sys.stdin.buffer.read
#input = sys.stdin.buffer.readline
#inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	q=deque()
	check=set()
	a=[None]*(n+1)

	for i in range(1,n+1):
		if i in check:
			continue
		elif li[i]==[]:
			continue
		else:
			q=[i]
			a[i]=0
			while q:
				now=q.pop()
				check.add(now)
				for r,d in li[now]:
					if r in check:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					elif r in q:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					else:
						a[r] = a[now] + d
						q.append(r)
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	q=deque()
	check=set()
	a=[None]*(n+1)

	for i in range(1,n+1):
		if i in check:
			continue
		elif li[i]==[]:
			continue
		else:
			q=[i]
			a[i]=0
			while q:
				now=q.pop()
				check.add(now)
				for r,d in li[now]:
					if r in check:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					elif r in q:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					else:
						a[r] = a[now] + d
						q.append(r)
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	q=deque()
	check=set()
	a=[""]*(n+1)

	for i in range(1,n+1):
		if i in check:
			continue
		elif li[i]==[]:
			continue
		else:
			q.append(i)
			a[i]=0
			while q:
				now=q.pop()
				check.add(now)
				for j in li[now]:
					r=j[0]
					d=j[1]
					if r in check:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					elif r in q:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					else:
						a[r] = a[now] + d
						q.append(r)
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[]
	li2=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li.append((l,r,d))
		#li.append((r,l,-d))
		li2[l].append((r,d))
		li2[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[""]*(n+1)

	for i in li:
		if i[0] in check:
			continue
		else:
			stack.append(i[0])
			a[i[0]]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li2[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[]
	li2=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li.append((l,r,d))
		li.append((r,l,-d))
		li2[l].append((r,d))
		li2[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[-10**10]*(n+1)

	for i in li:
		if i[0] in check:
			continue
		else:
			stack.append(i[0])
			a[i[0]]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li2[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for i in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[-10**10]*(n+1)
	
	for i in range(1,n+1):
		if li[i]==[""] or (i in check):
			continue
		else:
			stack.append(i)
			a[i]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for i in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	stack=[]
	check=set()
	a=["a"]*(n+1)
	
	for i in range(1,n+1):
		if li[i]==["a"] or (i in check):
			continue
		else:
			stack.append(i)
			a[i]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							#a[j[0]]=a[now]+j[1]
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in E.keys()}
    dis = [0]*(N+1)
    while False in visited.values():
        stk = [(list(visited.values()).index(False) + 1, -1, 0)]
        flag = True
        while stk:
            v, p, d = stk.pop()
            #print(v,p)
            if visited[v]:
                if dis[v]!=dis[p]+d:
                    print("No")
                    exit()
                continue
            visited[v] = True
            dis[v]=dis[p]+d
            for u,d in E[v]:
                if u != p:
                    stk.append((u,v,d))
    print("Yes")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    def inputs():
        return (int(x) for x in input().split())
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1,N+1)}
    dis = [0]*(N+1)
    while False in visited.values():
        stk = [(list(visited.values()).index(False) + 1, -1, 0)]
        flag = True
        while stk:
            v, p, d = stk.pop()
            #print(v,p)
            if visited[v]:
                if dis[v]!=dis[p]+d:
                    print("No")
                    exit()
                continue
            visited[v] = True
            dis[v]=dis[p]+d
            for u,d in E[v]:
                if u != p:
                    stk.append((u,v,d))
    print("Yes")
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():    
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    N,M = inputs()
    E={i:[] for i in range(1,N+1)}
    for i in range(M):
        L,R,D = inputs()
        E[L].append((R,D))
        E[R].append((L,-D))
    visited = {i: False for i in range(1, N+1)}
    counter = 0
    dis = [0]*(N+1)
    while False in visited.values():
        stk = [(list(visited.values()).index(False) + 1, -1, 0)]
        flag = True
        while stk:
            v, p, d = stk.pop()
            #print(v,p)
            if visited[v]:
                if dis[v]!=dis[p]+d:
                    print("No")
                    exit()
                continue
            visited[v] = True
            dis[v]=dis[p]+d
            for u,d in E[v]:
                if u != p:
                    stk.append((u,v,d))
    print("Yes")
main()

Submission status: Time Limit Exceeded

Solution code:
def inputs():
    return [int(x) for x in input().split()]
N,M = inputs()
E={i:[] for i in range(1,N+1)}
for i in range(M):
    L,R,D = inputs()
    E[L].append((R,D))
    E[R].append((L,-D))
visited = {i: False for i in range(1, N+1)}
counter = 0
dis = [0]*(N+1)
while False in visited.values():
    stk = [(list(visited.values()).index(False) + 1, -1, 0)]
    flag = True
    while stk:
        v, p, d = stk.pop()
        #print(v,p)
        if visited[v]:
            if dis[v]!=dis[p]+d:
                print("No")
                exit()
            continue
        visited[v] = True
        dis[v]=dis[p]+d
        for u,d in E[v]:
            if u != p:
                stk.append((u,v,d))
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import collections

n, m = map(int, input().split())
es = [collections.deque() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    es[l].append((l, r, d))
    es[r].append((r, l, -d))

visited = [False for _ in range(n)]
for i in range(n):
    if not visited[i]:
        visited[i] = True
        if len(es[i]) == 0:
            continue
        distances = [float('inf') for _ in range(n)]
        distances[i] = 0
        q = collections.deque()
        for e in es[i]:
            q.append(e)
        while q:
            j, k, d = q.popleft()
            if visited[k] and distances[k] != distances[j] + d:
                print('No')
                exit()
            distances[k] = distances[j] + d
            visited[k] = True
            while es[k]:
                ee = es[k].popleft()
                if len(es[ee[1]]) > 0:
                    q.append(ee)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import collections

n, m = map(int, input().split())
es = [collections.deque() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    es[l].append((l, r, d))
    es[r].append((r, l, -d))

visited = [False for _ in range(n)]
for i in range(n):
    if not visited[i]:
        visited[i] = True
        distances = [float('inf') for _ in range(n)]
        distances[i] = 0
        q = collections.deque()
        for e in es[i]:
            q.append(e)
        while q:
            j, k, d = q.popleft()
            if visited[k] and distances[k] != distances[j] + d:
                print('No')
                exit()
            distances[k] = distances[j] + d
            visited[k] = True
            while es[k]:
                ee = es[k].popleft()
                q.append(ee)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
E = [[] for _ in range(N)]
RE = [[] for _ in range(N)]
S = [0] * N
for _ in range(M):
  l, r, d = map(int, input().split())
  S[l - 1] = 1
  E[l - 1].append([d, r - 1])
  RE[r - 1].append([d, l - 1])
D = [None] * N
def dijkstra(i):
  D[i] = 0
  Q = [[0, i]]
  while Q:
    d, s = heapq.heappop(Q)
    for dist, adj in E[s]:
      if D[adj] == None:
        D[adj] = D[s] + dist
        heapq.heappush(Q, [D[adj], adj])
      elif D[adj] == 'Error' or D[adj] != D[s] + dist:
        D[s] = 'Error'
        break
    else:
      for dist, adj in RE[s]:
        if D[adj] == None:
          D[adj] = D[s] - dist
          heapq.heappush(Q, [D[adj], adj])
        elif D[adj] == 'Error' or D[adj] != D[s] - dist:
          D[s] = 'Error'
          break
      else:
        continue
    break
for i in range(N):
  if D[i] == 'Error':
    print('No')
    break
  elif D[i] == None:
    dijkstra(i)
else:
  for d in D:
    if d == 'Error':
      print('No')
      break
  else:
    print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def sol():
    n,m=map(int,input().split())
    t,w={},{}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        t[(l,r)]=d
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    #chk=set()
    chk=deque()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        #chk.add((i,0))
        chk.append((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=x[1]+j[1]:
                    #if (x[0],j[0]) in t and t[(i,j[0])]!=
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        t[(i,j[0])]=x[1]+j[1]
                        #chk.add((j[0],x[1]+j[1]))
                        chk.append((j[0],x[1]+j[1]))
                    else:
                        #chk.add((j[0],x[1]+j[1]))
                        chk.append((j[0],x[1]+j[1]))
    print("Yes")

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    n,m=map(int,input().split())
    t={}
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        t[(l,r)]=d
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    chk=set()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        chk.add((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=x[1]+j[1]:
                    #if (x[0],j[0]) in t and t[(i,j[0])]!=
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        t[(i,j[0])]=x[1]+j[1]
                        chk.add((j[0],x[1]+j[1]))
                    else:
                        chk.add((j[0],x[1]+j[1]))
    print("Yes")

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
t={}
w={}
p,q=set(),set()
for i in range(m):
    l,r,d=[int(i) for i in input().split()]
    t[(l,r)]=d
    if l in w:
        w[l].add((r,d))
    else:
        w[l]={(r,d)}
    p.add(l)
    q.add(r)
s=p-q
chk=set()
if len(s)==0:
    print(["No","Yes"][m==0])
    exit()
for i in s:
    chk.add((i,0))
    while len(chk):
        x=chk.pop()
        if x[0] in w:
            for j in w[x[0]]:
                if (i,j[0]) in t and t[(i,j[0])]!=x[1]+j[1]:
                #if (x[0],j[0]) in t and t[(i,j[0])]!=
                    print("No")
                    exit()
                elif (i,j[0]) not in t:
                    t[(i,j[0])]=x[1]+j[1]
                    chk.add((j[0],x[1]+j[1]))
                else:
                    chk.add((j[0],x[1]+j[1]))
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n,q = m()

data = [l() for i in range(q)]

edges = [[] for i in range(n)]

for a,b,c in data:
    edges[a-1].append([b-1,c])
    edges[b-1].append([a-1,-c])

num = [0 for _ in range(n)]

Ma,mi = 0,0

vi = [False for i in range(n)]
ans = 0

for i in range(n):
    if vi[i]:
        continue
    stack = [i]
    vi[i] = True
    while stack:
        v = stack.pop()
        for e,r in edges[v]:
            if not vi[e]:
                num[e] = num[v] + r
                stack.append(e)
                vi[e] = True

for i in range(n):
    if num[i] < mi:
        mi = num[i]
    elif num[i] > Ma:
        Ma = num[i]
    for e,r in edges[i]:
        if num[i] + r != num[e]:
            ans = -1
            break
    else:
        continue
    break
else:
    print("Yes")
    exit()
print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = defaultdict(lambda: [])
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()

    for i in range(1, N + 1):
        if seen[i] == 0:
            dfs(adj, i)

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()

    for i in range(1, N + 1):
        if seen[i] == 0:
            dfs(adj, i)

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, seen, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()
        return seen

    for i in range(1, N + 1):
        if seen[i] == 0:
            seen = dfs(adj, seen, i)

    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    adj[L].append((R, D))
    adj[R].append((L, -D))
seen = [0] * (N + 1)


def dfs(adj, seen, start):
    inf = 10 ** 10
    que = deque()
    que.append(start)
    x = [inf] * (N + 1)
    x[start] = 0
    while que:
        v = que.pop()
        seen[v] = 1
        for u, d in adj[v]:
            if seen[u] == 0:
                que.append(u)
                if x[u] == inf:
                    x[u] = x[v] + d
                else:
                    if x[u] != x[v] + d:
                        print('No')
                        sys.exit()
    return seen


for i in range(1, N + 1):
    if seen[i] == 0:
        seen = dfs(adj, seen, i)

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    adj[L].append((R, D))
    adj[R].append((L, -D))
seen = [0] * (N + 1)


def dfs(adj, seen, start):
    inf = 10 ** 10
    que = deque()
    que.append(start)
    x = [inf] * (N + 1)
    x[start] = 0
    while que:
        v = que.pop()
        seen[v] = 1
        for u, d in adj[v]:
            if seen[u] == 0:
                que.append(u)
                if x[u] == inf:
                    x[u] = x[v] + d
                else:
                    if x[u] != x[v] + d:
                        return 0, seen
    return 1, seen


for i in range(1, N + 1):
    if seen[i] == 0:
        ok, seen = dfs(adj, seen, i)
        if not ok:
            print('No')
            sys.exit()

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    adj[L].append((R, D))
    adj[R].append((L, -D))
seen = [0] * (N + 1)


def dfs(adj, seen, start):
    inf = 10 ** 10
    que = deque()
    que.append(start)
    x = [inf] * (N + 1)
    x[start] = 0
    while que:
        v = que.pop()
        seen[v] = 1
        for u, d in adj[v]:
            if seen[u] == 0:
                que.append(u)
                if x[u] == inf:
                    x[u] = x[v] + d
                else:
                    if x[u] != x[v] + d:
                        return 0, seen
    return 1, seen


for i in range(1, N + 1):
    if seen[i] == 0:
        ok, seen = dfs(adj, seen, i)
        if not ok:
            print('No')
            sys.exit()

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class Node:
    def __init__(self, id):
        self.id = id
        self.is_root = True
        self.parent = None
        self.distance = 0
    
    def root_node(self):
        node = self
        distance_to_root = 0
        while not node.is_root:
            distance_to_root += node.distance
            node = node.parent
        return node, distance_to_root

def main():
    N, M = map(int, input().split())
    lrd = [list(map(int, input().split())) for i in range(M)]

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

    ok = True
    for i in range(M):
        l, r, d = lrd[i]
        # print(l, r, d)
        root_l, dist_l = nodes[l].root_node()
        root_r, dist_r = nodes[r].root_node()
        if root_l == root_r:# 根が同じ場合はdが正しいか判定する
            # print(root_l.id, dist_l)
            # print(root_r.id, dist_r)
            if dist_l + d != dist_r:
                ok = False
                break
        else:
            root_r.is_root = False
            root_r.distance = dist_l + d - dist_r
            root_r.parent = root_l
    
    if ok:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()