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:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    # table[ind] は ind の親の index を表す。ind == table[ind] の時そのグループの root である。
            self.rank = [0] * self.n    # root となる ind について rank[ind] はその木の深さを表す。それ以外の ind については意味を持たない。
            self.group_size = [1] * self.n    # root となる ind について group_size[ind] はそのグループに属するメンバの個数を表す。それ以外の ind については意味を持たない。
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])

    
    def dfs_and_check_no_contradict(start, info, dist_list, visited):
        stack = [start]
        while stack:
            u = stack[-1]
            for v, dist in info[u]:
                if dist_list[v] is None:
                    dist_list[v] = dist_list[u] + dist
                elif dist_list[v] != dist_list[u] + dist:
                    return False
            for v, dist in info[u]:
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)
                    break
            else:
                stack.pop()
        return True
            


    def no_contradict_p(info):
        uf = UnionFindTree(n)
        for l in range(n):
            for r, _ in info[l]:
                uf.union(l, r)
        
        for ind, g in enumerate(uf.table):
            if ind == g:
                dist_list = [None] * n
                dist_list[g] = 0
                visited = [False] * n
                visited[g] = True
                if not dfs_and_check_no_contradict(g, info, dist_list, visited):
                    return False
        # # 距離関係の矛盾は今のところなかった。あとは座標のレンジがおさまるかチェック
        # for g, d in point_dict.items():
        #     if max(d.values()) -  min(d.values()) > 10**9:    # どうスライド移動しても入らない
        #         return False
        return True

    
    n, m = mi()
    info = [[] for _ in range(n)]
    for _ in range(m):
        l, r, dist = mi_0()
        dist += 1
        info[l].append((r, dist))
        info[r].append((l, -dist))
    
    print('Yes') if no_contradict_p(info) else print('No')



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    # table[ind] は ind の親の index を表す。ind == table[ind] の時そのグループの root である。
            self.rank = [0] * self.n    # root となる ind について rank[ind] はその木の深さを表す。それ以外の ind については意味を持たない。
            self.group_size = [1] * self.n    # root となる ind について group_size[ind] はそのグループに属するメンバの個数を表す。それ以外の ind については意味を持たない。
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])

    
    def dfs_and_check_no_contradict(current, info, point_dict, visited):
        visited[current] = True
        for v, dist in info[current]:
            if v in point_dict and point_dict[current] + dist != point_dict[v]:
                return False
            if not visited[v]:
                point_dict[v] = point_dict[current] + dist
                result = dfs_and_check_no_contradict(v, info, point_dict, visited)
                if not result:
                    return False
        return True
            


    def no_contradict_p(info):
        uf = UnionFindTree(n)
        for l in range(n):
            for r, _ in info[l]:
                uf.union(l, r)
        
        for ind, g in enumerate(uf.table):
            if ind == g:
                point_dict = {g: 0}
                visited = [False] * n
                if not dfs_and_check_no_contradict(g, info, point_dict, visited):
                    return False
        # # 距離関係の矛盾は今のところなかった。あとは座標のレンジがおさまるかチェック
        # for g, d in point_dict.items():
        #     if max(d.values()) -  min(d.values()) > 10**9:    # どうスライド移動しても入らない
        #         return False
        return True

    
    n, m = mi()
    info = [[] for _ in range(n)]
    for _ in range(m):
        l, r, dist = mi_0()
        dist += 1
        info[l].append((r, dist))
        info[r].append((l, -dist))
    
    print('Yes') if no_contradict_p(info) else print('No')



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def inputs(func=lambda x: x, sep=None, maxsplit=-1):
	return map(func, input().split(sep=sep, maxsplit=maxsplit))

def input_row(n : int, type=np.int, *args, **kwargs):
	return np.fromiter(inputs(type, *args, **kwargs), dtype=type)

def input_2d(nrows : int, ncols : int, type=np.int, *args, **kwargs):
	data = np.zeros((nrows, ncols), dtype=type)
	for i in range(nrows):
		data[i, :] = input_row(ncols, type, *args, **kwargs)
	return data

class IntAddition (object):
	'''整数の加法'''
	def operate(self, x, y):
		return x + y
	@property
	def identity(self):
		return 0
	def cancel(self, x, y):
		return x - y
	def invert(self, x):
		return -x
	def accumulate(self, x, count):
		return x * count

class UnionFindNode (object):
	__slots__ = [
		'parent_index',
		'size',
		'difference_from_parent'
	]
	
	def __init__(self, index : int, potential_identity):
		self.parent_index = index
		self.size = 1
		self.difference_from_parent = potential_identity

class UnionFind (object):
	'''重み付きUnion-Find木'''
	def __init__(
			self,
			num_nodes=0,
			potential_abelian=IntAddition()):
		self.nodes = []
		self.op = potential_abelian
		
		self.extend(num_nodes)
	
	def append(self):
		self.nodes.append(
			UnionFindNode(len(self.nodes), self.op.identity)
		)
		
	def extend(self, num_nodes):
		self.nodes.extend(
			UnionFindNode(i, self.op.identity)
			for i in range(num_nodes)
		)
	
	def root(self, index : int):
		x = self.nodes[index]
		
		while x.parent_index != index:
			parent = self.nodes[x.parent_index]
			x.difference_from_parent = self.op.operate(
				x.difference_from_parent,
				parent.difference_from_parent
			)
			index = x.parent_index = parent.parent_index
			x = self.nodes[index]
		
		return index
	
	def difference_from_root_to(self, index : int):
		x = self.nodes[index]
		potential = x.difference_from_parent
		
		while x.parent_index != index:
			parent = self.nodes[x.parent_index]
			potential = self.op.operate(
				potential,
				parent.difference_from_parent
			)
			index = x.parent_index
			x = self.nodes[index]
		
		return potential
		
	def size(self, index : int):
		return self.nodes[self.root(index)].size
	
	def difference(self, x, y):
		if not self.issame(x, y):
			raise RuntimeError('x と y は同じ集合に属していません。')
		return self.op.cancel(
			self.difference_from_root_to(y),
			self.difference_from_root_to(x)
		)
	
	def unite(self, x, y, difference=None) -> bool:
		if difference is None:
			difference = self.op.identity
		
		x, px = self.root(x), self.difference_from_root_to(x)
		y, py = self.root(y), self.difference_from_root_to(y)
		if x == y:
			return difference == self.op.cancel(py, px)
		
		difference = self.op.cancel(difference, py)
		difference = self.op.operate(difference, px)
		
		if self.size(x) < self.size(y):
			x, y = y, x
			difference = self.op.invert(difference)
		
		x_node = self.nodes[x]
		y_node = self.nodes[y]
		x_node.size += y_node.size
		y_node.parent_index = x
		y_node.difference_from_parent = difference
		
		return True
	
	def issame(self, x, y):
		return self.root(x) == self.root(y)



N, M = inputs(int)
uf = UnionFind(num_nodes=N)

valid = True
for i in range(M):
	L, R, D = inputs(int)
	L -= 1
	R -= 1
	
	valid = valid and uf.unite(L, R, D)

print('Yes' if valid else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
if m==0:
    print("Yes")
    sys.exit()

tree = [[] for _i in range(n+1)]
for _i in range(m):
    l, r, d = map(int, input().split())
    tree[l].append([r, d])
    tree[r].append([l, -d])

from collections import deque
INF = "INF"
visit = [INF for _i in range(n+1)]
for i in range(1, n+1):
    if visit[i]==INF:
        visit[i] = 0
    else:
        continue
    q = deque([i])
    while q:
        p = q.popleft()
        if visit[p]==INF:
            visit[p] = 0
        for i, j in tree[p]:
            if i==p:
                continue
            elif visit[i] == INF:
                visit[i] = visit[p]+j
                q.append(i)
            elif visit[i] == visit[p]+j:
                continue
            else:
                print("No")
                sys.exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
dist=[float("inf")]*N
tree=[[] for _ in range(N)]
table=[[float("inf") for _ in range(N)] for _ in range(N)]
flag=1
for i in range(M):
    l,r,d=map(int,input().split())
    tree[l-1].append(r-1)
    tree[r-1].append(l-1)
    table[l-1][r-1]=d
    table[r-1][l-1]=-d
#print(tree)
for i in range(N):
    d=deque()
    if dist[i]==float("inf"):
        dist[i]=0
    d.append(i)
    v=d.popleft()
    for j in tree[v]:
        if dist[j]==float("inf"):
            dist[j]=dist[v]+table[v][j]
        elif dist[j]!=dist[v]+table[v][j]:
            flag=0
            break
        #print(dist)
    if flag==0:
        break
    #print(dist)
    #input()
if flag==1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

    for i in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        e[a].append([b,c])
        e[b].append([a,-c])


    dis = [False]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append((x,0))
        while q:
            now,cnt = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == False:
                    dis[nex] = cnt+d
                    q.append((nex,cnt+d))
                else:
                    if dis[nex] != cnt+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == False:
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

    for i in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        e[a].append([b,c])
        e[b].append([a,-c])


    dis = [False]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append(x)
        while q:
            now = q.popleft()
            for nex,d in e[now]:
                if dis[nex] == False:
                    dis[nex] = dis[now]+d
                    q.append(nex)
                else:
                    if dis[nex] != dis[now]+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == False:
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():    
    from collections import deque
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    e = [[] for i in range(n)]

    for i in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        e[a].append([b,c])
        e[b].append([a,-c])


    dis = [False]*n

    def search(x):

        q = deque([])
        dis[x] = 0
        q.append(x)
        while q:
            now = q.pop()
            for nex,d in e[now]:
                if dis[nex] == False:
                    dis[nex] = dis[now]+d
                    q.append(nex)
                else:
                    if dis[nex] != dis[now]+d:
                        print("No")
                        exit()
            
    for i in range(n):
        if e[i] and dis[i] == False:
            search(i)
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m = map(int,input().split())
e = [[] for i in range(n)]

for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append([b,c])
    e[b].append([a,-c])


dis = [False]*n

def search(x):

    q = deque([])
    dis[x] = 0
    q.append(x)
    while q:
        now = q.pop()
        for nex,d in e[now]:
            if dis[nex] == False:
                dis[nex] = dis[now]+d
                q.append(nex)
            else:
                if dis[nex] != dis[now]+d:
                    print("No")
                    exit()
        
for i in range(n):
    if e[i] and dis[i] == False:
        search(i)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
INF = 10 ** 10
from collections import deque
# 頂点、親、距離
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  q = deque()
  q.append([i,-1,0])
  while q:
    v,parent,d = q.popleft()
#    print("v",v,"dist[v]",dist[v],"d",d)
    if dist[v] == INF:
      # 初めてくる場所
      dist[v] = d
    else:
      # 初めてではない場合
      if dist[v] != d:
        print("No")
        exit(0)
      else:
        continue
    for child in E[v]:
      if child == parent:
        continue
      q.append([child[0],v,d + child[1]])
else:
  print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
dist=[float("inf")]*N
tree=[[] for _ in range(N)]
table=[[float("inf") for _ in range(N)] for _ in range(N)]
flag=1
for i in range(M):
    l,r,d=map(int,input().split())
    tree[l-1].append(r-1)
    tree[r-1].append(l-1)
    table[l-1][r-1]=d
    table[r-1][l-1]=-d
#print(tree)
for i in range(N):
    d=deque()
    if dist[i]==float("inf"):
        dist[i]=0
    d.append(i)
    while (len(d)>0)and(flag==1):
        v=d.popleft()
        for j in tree[v]:
            if dist[j]==float("inf"):
                dist[j]=dist[v]+table[v][j]
            elif dist[j]!=dist[v]+table[v][j]:
                flag=0
                break
    if flag==0:
        break
    #print(dist)
    #input()
if flag==1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  for j,d in graph[i]:
    if ans[j]-ans[i]!=d:
      print("No")
      exit()
    else:
      continue

print("Yes")

Submission status: Time Limit Exceeded

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

ans=[0]*N
D=[[0]*N for _ in range(N)]
graph=[[] for _ in range(N)]
for i in range(M):
  L,R,d=map(int,input().split())
  L,R=L-1,R-1
  D[L][R]=d
  D[R][L]=-d
  ans[R]=ans[L]+D[L][R]
  graph[L].append(R)
  graph[R].append(L)
  for j in graph[R]:
    if ans[R]-ans[j]!=D[j][R]:
      print("No")
      exit()
    else:
      continue
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#辞書でデータを持たずに、配列のindexに対応して値を持ったほうが良い
#例）
#dic={}
#dic[1]=[1,2]
#hairetsu =[]*n
#hairetsu[1]=[1,2]
#大きい数字はMLEやTLEにつながる

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

n,m=map(int,input().split())

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

n,m=map(int,input().split())

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    #print("lrd",lrd)
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

#print(lrd)

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = ["first"]*n
        answer[i]=1
        BFD(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=10**10
MOD=10**9+7
input=sys.stdin.readline

n,m=map(int,input().split())

#初期値が0の辞書
#from collections import defaultdict
#lrd = defaultdict(lambda: []) 

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    #print("lrd",lrd)
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

#print(lrd)

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]==-10**10:
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = [-10**10]*n
        answer[i]=1
        BFD(i)

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=10**10
MOD=10**9+7
input=sys.stdin.readline

n,m=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
lrd = defaultdict(lambda: []) 

lr=defaultdict(lambda: 0) 

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x)
    for llrrdd in lrd[x]:
        #print(lrd,item,x)
        item=llrrdd[0]
        if answer[item]==INF:
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = defaultdict(lambda: INF) 
        answer[i]=1
        BFD(i)

print("Yes")