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
sys.setrecursionlimit(2147483647)
INF=float('inf')
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")

Submission status: Time Limit Exceeded

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

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

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

yx=[[0]*n for _ in range(n)]

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



def BFD(x):
    global checked,answer
    checked[x]=1
    #print("x>>>",x)
    for item in lrd[x]:
        #print(lrd,item,x)
        ll=min(item,x)
        rr=max(item,x)
        if answer[item]==-1:
            if item<=x:
                answer[item]=answer[x]-yx[item][x]
            else:
                answer[item]=answer[x]+yx[x][item]
        else:
            if answer[rr]!=answer[ll]+yx[ll][rr]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

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

print("Yes")

Submission status: Time Limit Exceeded

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

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

yx=[[0]*n for _ in range(n)]

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



def BFD(x):
    global checked,answer
    checked[x]=1
    #print("x>>>",x)
    for item in lrd[x]:
        #print(lrd,item,x)
        ll=min(item,x)
        rr=max(item,x)
        if answer[item]==-1:
            if item<=x:
                answer[item]=answer[x]-yx[item][x]
            else:
                answer[item]=answer[x]+yx[x][item]
        else:
            if answer[rr]!=answer[ll]+yx[ll][rr]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

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

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = deque([])
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            L_R_D_arr.append(_)
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        iter_ = [float('inf')]*(N+1)
        iter_[L_R_D_arr[0][0]] = 0
        
        TF = 'No'
        rot_cnt = 0
        while len(L_R_D_arr)>0:
            if rot_cnt > len(L_R_D_arr):
                iter_ = [float('inf')]*(N+1)
                iter_[L_R_D_arr[0][0]] = 0
            else:
                L, R, D = L_R_D_arr[0]
                if iter_[L] == float('inf'):
                    if iter_[R] == float('inf'):
                        L_R_D_arr.rotate(-1)
                        rot_cnt += 1
                    else:
                        iter_[L] = iter_[R]-D
                        L_R_D_arr.popleft()
                        rot_cnt = 0
                else:
                    rot_cnt = 0
                    if iter_[R] == float('inf'):
                        iter_[R] = iter_[L]+D
                        L_R_D_arr.popleft()
                    elif iter_[R] == iter_[L]+D:
                        L_R_D_arr.popleft()
                    else:
                        break
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = []
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            L_R_D_arr.append(_)
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        L_R_D_arr.sort()
        L_R_D_arr = deque(L_R_D_arr)
        iter_ = [float('inf')]*(N+1)

        TF = 'No'
        iter_[L_R_D_arr[0][0]] = 0
        rot_cnt = 0
        while len(L_R_D_arr)>0:
            if rot_cnt > len(L_R_D_arr):
                iter_ = [float('inf')]*(N+1)
                iter_[L_R_D_arr[0][0]] = 0
            else:
                L, R, D = L_R_D_arr[0]
                if iter_[L] == float('inf'):
                    if iter_[R] == float('inf'):
                        L_R_D_arr.rotate(-1)
                        rot_cnt += 1
                    else:
                        iter_[L] = iter_[R]-D
                        L_R_D_arr.popleft()
                        rot_cnt = 0
                else:
                    rot_cnt = 0
                    if iter_[R] == float('inf'):
                        iter_[R] = iter_[L]+D
                        L_R_D_arr.popleft()
                    elif iter_[R] == iter_[L]+D:
                        L_R_D_arr.popleft()
                    else:
                        break
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    
    if M == 0:
        TF = 'Yes'
    else:
        L_R_D_arr = []
        for i in range(M):
            _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
            L_R_D_arr.append(_)
        # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
        L_R_D_arr.sort()
        L_R_D_arr = deque(L_R_D_arr)
        iter_ = [float('inf')]*(N+1)

        TF = 'No'
        iter_[L_R_D_arr[0][0]] = 0
        while len(L_R_D_arr)>0:
            L, R, D = L_R_D_arr[0]
            if iter_[L] == float('inf'):
                if iter_[R] == float('inf'):
                    L_R_D_arr.rotate(-1)
                else:
                    iter_[L] = iter_[R]-D
                    L_R_D_arr.popleft()
            else:
                if iter_[R] == float('inf'):
                    iter_[R] = iter_[L]+D
                    L_R_D_arr.popleft()
                elif iter_[R] != iter_[L]+D:
                    break
                else:
                    L_R_D_arr.popleft()
        else:
            TF = 'Yes'
        # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,-R,D))
    merge(L,R)
  else:
    lrdlist.append((R,-L,-D))  
    merge(R,L)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

lrdlist2=[]
while(len(lrdlist)>0):
  lrdlist2=[]
  for L,R,D in lrdlist:
    R=-R
    if array[L]==-10**9:
      if array[R]==-10**9:
        lrdlist2.append((L,-R,D))
      else:
        array[L]=array[R]-D
    else:
      if array[R]==-10**9:
        array[R]=array[L]+D
      else:
        if array[R]!=array[L]+D:
          print("No")
          sys.exit(0)
  lrdlist=lrdlist2

#print(array[1:])
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
    merge(L,R)
  else:
    lrdlist.append((R,L,-D))  
    merge(R,L)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

lrdlist2=[]
while(len(lrdlist)>0):
  lrdlist2=[]
  for L,R,D in lrdlist:
    if array[L]==-10**9:
      if array[R]==-10**9:
        lrdlist2.append((L,R,D))
      else:
        array[L]=array[R]-D
    else:
      if array[R]==-10**9:
        array[R]=array[L]+D
      else:
        if array[R]!=array[L]+D:
          print("No")
          sys.exit(0)
  lrdlist=lrdlist2

#print(array[1:])
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

def is_same(x,y):
  return get_par(x) == get_par(y)

N,M=map(int,input().split())
par_list = list(range(N+1))

lrdlist=[]
for i in range(M):
  L,R,D=map(int,input().split())
  if L<R:
    lrdlist.append((L,R,D))
    merge(L,R)
  else:
    lrdlist.append((R,L,-D))  
    merge(R,L)
lrdlist.sort()
#print(lrdlist)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)

array=[0]+[-10**9]*(N)
for i in range(1,N+1):
  if par_list[i]==i:
    array[i]=0
#print(array)

lrdlist2=[]
while(len(lrdlist)>0):
  lrdlist2=[]
  for L,R,D in lrdlist:
    if array[L]==-10**9:
      if array[R]==-10**9:
        lrdlist2.append((L,R,D))
      else:
        array[L]=array[R]-D
    else:
      if array[R]==-10**9:
        array[R]=array[L]+D
      else:
        if array[R]!=array[L]+D:
          print("No")
          sys.exit(0)
  lrdlist=lrdlist2

#print(array[1:])
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# 12:17-12:28 give up -> kaisetu
# 13:18-14:08 chudan
# 15:29-16:06

# from time import time
# import sys

# sys.setrecursionlimit(10000)


def main():
    N, M = map(int, input().split())
    L, R, D = [None] * M, [None] * M, [None] * M
    for i in range(M):
        L[i], R[i], D[i] = map(int, input().split())
        L[i] -= 1  # 1-index -> 0_index
        R[i] -= 1  # 1-index -> 0_index

    dist_infos = {}
    for l, r, d in zip(L, R, D):
        if l in dist_infos:
            dist_infos[l][r] = d
        else:
            dist_infos[l] = {r: d}

        if r in dist_infos:
            dist_infos[r][l] = -d
        else:
            dist_infos[r] = {l: -d}

    xs = [None] * N

    # ========================================
    # fixed = set([])
    # n_fixed = [0]

    # def rec(node):
    #     # global n_fixed

    #     fixed.add(node)
    #     n_fixed[0] += 1

    #     if xs[node] is None:  # if start node
    #         xs[node] = 0
        
    #     if xs[node] is None and node not in dist_infos:  # if isolated
    #         return None
        
    #     # if 
        
    #     # 隣接するノードでまだfixしていないもの
    #     adj_node_infos = {
    #         adj: d for adj, d in dist_infos[node].items() if adj not in fixed
    #     }

    #     for adj, d in adj_node_infos.items():
    #         if xs[adj] is None:
    #             xs[adj] = xs[node] + d
    #         elif xs[adj] != xs[node] + d:
    #             print("No")
    #             exit()

    #         rec(adj)

    # for key in dist_infos.keys():
    #     rec(key)

    # print("Yes")
    # ========================================

    # ========================================
    node_queue = [0]
    n_queue = 1
    fixed = set([])
    n_fixed = 0
    while True:
        if n_queue == 0:
            if n_fixed == N:
                return "Yes"

            for i in range(N):
                if xs[i] is None:
                    node_queue.append(i)
                    n_queue += 1
                    break
        
        # print(n_queue, node_queue, xs)
        node = node_queue[-1]
        del node_queue[-1]
        n_queue -= 1
        fixed.add(node)
        n_fixed += 1

        if xs[node] is None:  # start node
            xs[node] = 0
            if node not in dist_infos:  # start and terminal
                continue

        adj_node_infos = {
            k: d for k, d in dist_infos[node].items() if k not in fixed
        }

        for adj, d in adj_node_infos.items():
            if xs[adj] is None:
                xs[adj] = xs[node] + d
            elif xs[adj] != xs[node] + d:
                return "No"

            if adj not in node_queue:
                node_queue.append(adj)
                n_queue += 1
    
    return "Yes"
    # ========================================

    # def rec(node):
    #     if node not in dist_infos:
    #         pass  # ?

    #     for next_node, d in next_node_infos.items():
    #         if xs[next_nodes] is None:
    #             xs[next_nodes] = xs[node] + d
    #         elif xs[next_nodes] != xs[node] + d:
    #             return "No"
            
    #         fixed.append(next_node)
            
    #         return rec(next_node)

    # while True:
    #     if i not in dist_infos:
    #         continue

    #     if xs[i] is None:
    #         xs[i] = 0

    #     infos = {node: d for node, d in dist_infos[i].items() if node > i}

    #     for node, d in infos.items():
    #         if xs[node] is None:
    #             xs[node] = xs[i] + d
    #         elif xs[node] != xs[i] + d:
    #             return "No"

    # return "Yes"


# main()
# start = time()
print(main())
# print(time()-start)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# 12:17-12:28 give up -> kaisetu
# 13:18-14:08 chudan
# 15:29-16:14


def main():
    N, M = map(int, input().split())
    L, R, D = [None] * M, [None] * M, [None] * M
    for i in range(M):
        L[i], R[i], D[i] = map(int, input().split())
        L[i] -= 1  # 1-index -> 0_index
        R[i] -= 1  # 1-index -> 0_index

    dist_infos = {}
    for l, r, d in zip(L, R, D):
        if l in dist_infos:
            dist_infos[l][r] = d
        else:
            dist_infos[l] = {r: d}

        if r in dist_infos:
            dist_infos[r][l] = -d
        else:
            dist_infos[r] = {l: -d}

    xs = [None] * N

    node_queue = [0]
    n_queue = 1
    fixed = set([])
    n_fixed = 0
    while True:
        if n_queue == 0:
            if n_fixed == N:
                return "Yes"

            for i in range(N):
                if xs[i] is None:
                    node_queue.append(i)
                    n_queue += 1
                    break
        
        node = node_queue[-1]
        del node_queue[-1]
        n_queue -= 1
        fixed.add(node)
        n_fixed += 1
        
        if node not in dist_infos:
            # start and terminal
            xs[node] = 0
            continue

        if xs[node] is None:
            xs[node] = 0

        adj_node_infos = {
            k: d for k, d in dist_infos[node].items() if k not in fixed
        }

        for adj, d in adj_node_infos.items():
            if xs[adj] is None:
                xs[adj] = xs[node] + d
            elif xs[adj] != xs[node] + d:
                return "No"

            if adj not in node_queue:
                node_queue.append(adj)
                n_queue += 1


print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

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

    #[行先, 距離]
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        l,r,d = map(int, input().split())
        adj[l-1].append([r-1, d])
        adj[r-1].append([l-1, -d])

    x = [inf]*n

    def dfs(v):
        if x[v]==inf:
            x[v] = 0
        d = deque([v])
        while d:
            v  = d.popleft()
            for nv, cost in adj[v]:
                if x[nv] == inf:
                    x[nv] = x[v] + cost
                else:
                    if x[nv] - x[v] != cost:
                        return False
                d.append(nv)
        return True


    for v in range(n):
        if not dfs(v):
            print('No')
            exit()
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
LRD = []
for _ in range(M):
    LRD.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in LRD:
    l, r, d = el
    G[l].append((r, d))
    G[r].append((l, -d))
#print(G)

seen = [False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child, dist in G[parent]:
        group[-1].append((parent, child, dist))
        if seen[child] == False:
            dfs(child)


group =[]
for i in range(1, N + 1):
    if seen[i] == False:
        group.append([])
        dfs(i)
#print(group)

mujun = 0
zahyo = [None] * (N + 1)
for lst in group:
    if len(lst) > 2:
        zahyo[lst[0][0]] = 0
        for relation in lst:
            #print(zahyo)
            l, r, dist = relation
            if zahyo[r] != None:
                if zahyo[l] + dist != zahyo[r]:
                    mujun = 1
            else:
                zahyo[r] = zahyo[l] + dist

if mujun == 1:
    print('No')
else:
    print('Yes')

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [False] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 1
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == False:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [0] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 1
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == 0:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [0] * n
visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    d[i] = 0
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == 0:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [0] * n

for i in range(n):
    if d[i] != 0:
        continue
    stack = [i]
    while stack:
        u = stack.pop()
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
    d[i] = 1
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [0] * n
from collections import deque

queue = deque([])

for i in range(n):
    if d[i] != 0:
        continue
    queue.append(i)
    while queue:
        u = queue.popleft()
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                queue.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
    d[i] = 1
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

d = [0] * n

for i in range(n):
    if d[i] != 0:
        continue
    stack = [i]
    while stack:
        u = stack.pop()
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
    d[i] = 1
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

visited = [0] * n
d = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    d[i] = 0
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            visited[v] = 1
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    d[i] = 0
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            visited[v] = 1
            if d[v] == 0:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    d[i] = 0
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            visited[v] = 1
            if d[v] == 0:
                d[v] = d[u] + d_
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
        if g[u] and v != i:
            stack.append(v)
print("Yes")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    d[i] = 0
    stack = [i]
    while stack:
        u = stack.pop()
        for v, d_ in g[u]:
            visited[v] = 1
            if d[v] == 0:
                d[v] = d[u] + d_
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
        if g[u] and v != i:
            stack.append(v)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
class UF_weighed:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n+1))
        self.rank = [0]*(n+1)
        self.size = [1]*(n+1)
        self.diff_w = [0]*(n+1)

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

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

    def diff(self, x, y):
        if not self.same(x, y): return None
        return self.weight(y) - self.weight(x)

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

    def merge(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y, w = y, x, -w
        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.diff_w[y] = w
        return True
      
def main():
  n,m = map(int, input().split())
  uf = UF_weighed(n+1)
  q = [map(int, input().split()) for _ in range(m)]
  for a, b, c in q:
    if uf.same(a, b) and uf.diff(a, b) != c:
      return 'No'
    uf.merge(a, b, c)
  return 'Yes'

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