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: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = IR(3)
    a -= b
    print(a % c)
    return

#B
def B():
    a, b, c, x, ans = II(), II(), II(), II(), 0
    for i in range(a + 1):
        for j in range(b + 1):
            for k in range(c + 1):
                if i * 500 + j * 100 + k * 50 == x:
                    ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(2)]
    for i in range(1, n + 1):
        dp[0][i] += dp[0][i - 1] + a[i - 1]
    a = LI()
    for i in range(1, n + 1):
        dp[1][i] = max(dp[0][i], dp[1][i - 1]) + a[i - 1]
    print(dp[1][-1])
    
    return


class Value_UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.differ_weight[x] += self.differ_weight[self.par[x]]
        self.par[x] = r
        return r

    def weight(self, x):
        self.root(x)
        return self.differ_weight[x]

    def unit(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y, w = y, x, -w
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        self.differ_weight[y] = w
        return True

    def differ(self, x, y):
        return self.weight(y) - self.weight(x)
#D
def D():
    n, m = LI()
    u = Value_UnionFind(n)
    for _ in range(m):
        l, r, d = LI_()
        if not u.unit(l, r, d + 1):
            if differ(l, r) != d + 1:
                print("No")
                return
    print("Yes")


    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[[]for i in range(n+1)]
b=[""]*(n+1)
for i in range(m):
    l,r,d=map(int,input().split())
    a[l].append([r,d])
    a[r].append([l,-d])
for i in range(1,n+1):
    if b[i]=="":
        b[i]=0
        k=[i]
        while k:
            s=k.pop(i)
            for x,y in a[s]:
                if b[x]=="":
                    k.append(x)
                    b[x]=b[i]+y
c="Yes"
for i in range(1,n+1):
    for p,q in a:
        if a[i]+q!=p:
            c="No"
print(c)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[[]for i in range(n+1)]
b=[]for i in range(n):
for i in range(n):
    l,r,d=map(int,input().split())
    a[l].append([r,d])
    a[r].append([l,-d])
for i in range(1,n+1):
    if b[i]==None:
        b[i]=0
        k=[i]
        while k:
            s=k.pop(i)
            for x,y in a[s]:
                if b[x]==None:
                    k.append(x)
                    b[x]=b[i]+y
c="Yes"
for i in range(1,n+1):
    for p,q in a:
        if a[i]+q!=p:
            c="No"
print(c)

Submission status: Runtime Error

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

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

# print(nl)
    
seen = [None for _ in range(N + 1)]

def dfs(v, d):
    # print("dfs ", v, d)
    seen[v] = d
    for next_v, D in nl[v]:
        next_d = d + D
        if seen[next_v] is None:
            dfs(next_v, next_d)
        else:
            if seen[next_v] != next_d:
                print('No')
                exit(0)
                
for v in range(1, N + 1):  # すべての連結成分に対してDFS
    if seen[v] is None:
        dfs(v, 0)

print('Yes')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)

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


coord = [None for i in range(n)]
def dfs(v):
    possible = True
    for u, d in edges[v]:
        if coord[u]:
            if coord[u] != coord[v] + d:
                return False
        else:
            # not visited yet
            coord[u] = coord[v] + d
            possible = possible and dfs(u)

    return possible

ans = True
for i in range(n):
    if coord[i]:
        continue
    coord[i] = 0
    ans = ans and dfs(i)

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges[l].append((r, d))
    edges[r].append((l, -d))


coord = [None for i in range(n)]
def dfs(v):
    possible = True
    for u, d in edges[v]:
        if coord[u]:
            if coord[u] != coord[v] + d:
                return False
        else:
            # not visited yet
            coord[u] = coord[v] + d
            possible = possible and dfs(u)

    return possible

ans = True
for i in range(n):
    if coord[i]:
        continue
    coord[i] = 0
    ans = ans and dfs(i)

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
nl = [[] for _ in range(N + 1)]
for _ in range(M):
    L, R, D = map(int, input().split())
    nl[L].append((R, D))
    nl[R].append((L, -D))

seen = [None for _ in range(N + 1)]


def dfs(v, d):
    seen[v] = d
    for next_v, D in nl[v]:
        next_d = d + D
        if seen[next_v] is None:
            dfs(next_v, next_d)
        else:
            if seen[next_v] != next_d:
                print('No')
                exit(0)


for v in range(1, N + 1):  # すべての連結成分に対してDFS
    if seen[v] is None:
        dfs(v, 0)

print('Yes')

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input().split())
seq = []


for i in range(n):
    m = -1
    for j in range(len(s)):
        if int(s[j]) == j+1:
            m = j
    if m != -1:
        s = s[:m]+s[m+1:]
        seq.append(m+1)

print(s)
# print(seq)

if len(s) == 0:
    for i in range(1,n+1):
        print(seq[-i])
else:
    print("-1")

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] for _ in range(N+1)]

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [INF] * (N+1)

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] == INF:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        # if x[i] is not None: # 探索済み
        #     continue
        if x[i] == INF and dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] * (N+1) for _ in range(N+1) ]# 辺の保持

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [INF] * (N+1)

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] == INF:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        # if x[i] is not None: # 探索済み
        #     continue
        if x[i] == INF and dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] * (N+1) for _ in range(N+1) ]# 辺の保持

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [None] * (N+1)

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] is None:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        # if x[i] is not None: # 探索済み
        #     continue
        if x[i] is None and dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] * N for _ in range(N) ]# 辺の保持

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [None] * N

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] is None:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        # if x[i] is not None: # 探索済み
        #     continue
        if x[i] is None and dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] * N for _ in range(N) ]# 辺の保持

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [None] * N

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] is None:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] is None:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        if x[i] is not None: # 探索済み
            continue
        if dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] * N for _ in range(N) ]# 辺の保持

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append((Ri, Di))
        G[Ri].append((Li, -Di))

    # ある点からの距離
    x = [None] * N

    # 計算によって得たx[s]が正しいか
    def dfs(s, cost):
        # node_startまでの距離が未探索
        if x[s] is None:
            x[s] = cost
            # s->tの距離の整合性
            for t, d in G[s]:
                if dfs(t, cost + d) == False:
                    return False
        return x[s] == cost

    for i in range(N):
        if x[i] is not None: # 探索済み
            continue
        if dfs(i, 0) == False:
            print("No")
            return
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, M = l_inpl()

    G = [[] for _ in range(N)]

    for _ in range(M):
        Li, Ri, Di = l_inpl()
        Li, Ri = Li - 1, Ri - 1
        G[Li].append([Ri, Di])
        G[Ri].append([Li, -Di])

    # ある点からの距離
    x = [None] * N
    # 探索したことがあるか
    visited = [False] * N

    def dfs(current_node):
        visited[current_node] = True
        for t, d in G[current_node]:
            if visited[t]: # 探索済
                if x[t] != x[current_node] + d:
                    return False
            else: # 未探索
                x[t] = x[current_node] + d
                if not dfs(t): # なにこれ
                    return False
        return True

    for i in range(N):
        x[i] = 0
        if visited[i]: # 探索済み
            continue
        if not dfs(i):
            print("No")
            return            
    print("Yes")

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200002)


def dfs(s):
    global x, G
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            if not dfs(t):
                return False
        else:
            if x[t] != x[s] + d:
                return False
    return True


n, m = map(int, input().split())
x = [None] * n
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])
res = True
for i in range(n):
    if x[i] is None:
        x[i] = 0
        res &= dfs(i)
print('Yes' if res==True, else 'No')

Submission status: Runtime Error

Solution code:
def f(v,p,G,T):
    global ans
    INF = 10**10
    for C in G[v]:
        c,d = C[0],C[1]
        if T[c]==INF:
            T[c] = T[v]+d
            f(c,v,G,T)
        elif T[c]!=T[v]+d:
            ans = "No"
def main():
    global ans
    N,M = map(int,input().split())
    G = [[] for i in range(N+1)]
    for i in range(M):
        L,R,D = map(int,input().split())
        G[L].append([R,D])
        G[R].append([L,-D])
    INF = 10**10
    T = [INF]*(N+1)
    while T.count(INF)!=0:
        for i in range(N+1):
            if T[i] == INF:
                T[i]=0
                f(i,-1,G,T)
        if ans=="No":break
ans = "Yes"
main()
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]


n, m = map(int, input().split())
graph = defaultdict(list)
edges = []
l_nodes = set()
r_nodes = set()
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges.append((l, r, d))
    graph[l].append((d, r))
    l_nodes.add(l)
    r_nodes.add(r)

if m == 0:
    print("Yes")
else:
    x = l_nodes - r_nodes

    dist = dijkstra(graph, n, list(x)[0])
    possible = True
    for l, r, d in edges:
        if d != abs(dist[l] - dist[r]):
            possible = False
            break

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]


n, m = map(int, input().split())
graph = defaultdict(list)
edges = []
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges.append((l, r, d))
    graph[l].append((d, r))
    graph[r].append((d, l))


dist = dijkstra(graph, n, edges[0][0])
possible = True
for l, r, d in edges:
    if d != abs(dist[l] - dist[r]):
        possible = False
        break

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
e = [[] for i in range(N)]
t = 0
for i in range(M):
    r,l,d = map(int,input().split())
    e[r-1].append([l-1,d])
    e[l-1].append([r-1,-d])
    t = r-1

col = [ -1 for i in range(N) ]
def dfs(i,c):

    for node in e[i]:
        if col[node[0]] == -1:
            col[node[0]] = c + node[1]
            dfs(node[0],c+node[1])
        elif col[node[0]] != c + node[1]:
            print("No")
            exit()

dfs(t,0)

print("Yes")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
LRD = [list(map(int, input().split())) for _ in range(M)]

graph = [{} for _ in range(N)]
for l, r, d in LRD:
	l, r = l - 1, r - 1
	graph[l][r] = d
	graph[r][l] = -d

def dfs(v, p, d, depths):
	if depths[v] != -1:
		return True
	depths[v] = d

	for n in graph[v]:
		if n == p:
			continue
		n_depth = d + graph[v][n]
		if depths[n] != -1 and depths[n] != n_depth:
			return False
		result = dfs(n, v, n_depth, depths)
		if not result:
			return False
	return True

for n in range(N):
	if not dfs(n, -1, 0, [-1] * N):
		print("No")
		break
else:
	print("Yes")

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for _ in range(M)]
P = [[i, None] for i in range(1, N + 1)]
if M <= 1:
    print('Yes')
else:
    P[V[0][0] - 1][1] = 0
    for L, R, D in V:
        l_p = P[L - 1][1]
        r_p = P[R - 1][1]
        if r_p is None:
            P[R - 1] = [R, l_p + D]
        if l_p is None:
            P[L - 1] = [L, r_p - D]
        if r_p is not None and l_p is not None:
            if r_p - l_p != D:
                print('No')
                break
    else:
        print('Yes')

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
V = [[int(i) for i in input().split()] for _ in range(M)]
P = [[i, None] for i in range(1, N + 1)]
P[V[0][0] - 1][1] = 0
for L, R, D in V:
    l_p = P[L - 1][1]
    r_p = P[R - 1][1]
    if r_p is None:
        P[R - 1] = [R, l_p + D]
    if l_p is None:
        P[L - 1] = [L, r_p - D]
    if r_p is not None and l_p is not None:
        if r_p - l_p != D:
            print('No')
            break
else:
    print('Yes')

Submission status: Runtime Error

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

connect = [[] for _ in range(N)]
visited = [False for _ in range(N)]
cord = [0 for _ in range(N)]

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

def dfs(i):
    q = [i]
    
    while q:
        x = q.pop()
        for nx, d in connect[x]:
            if not visited[nx]:
                visited[nx] = True
                cord[nx] = cord[x] + d
                q.append(nx)
        else:
            if cord[nx] != cord[x] + d:
                return False
            
    return True

for i in range(N):
    if not visited[i]:
        visited[i] = True
        flag = dfs(i)
    if not flag:
        break

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

Submission status: Runtime Error

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

connect = [[] for _ in range(N)]
visited = [False for _ in range(N)]
cord = [0 for _ in range(N)]

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

def dfs(i,depth):
    for x, d in connect[i]:
        if not visited[x]:
            visited[x] = True
            cord[x] = depth + d
            dfs(x, cord[x])
        else:
            if cord[x] != depth + d:
                return False
    return True

for i in range(N):
    if not visited[i]:
        visited[i] = True
        flag = dfs(i, 0)
    if not flag:
        break

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

Submission status: Runtime Error

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

def dfs(v):
    for u, d in es[v]:
        if x[u] == None:
            x[u] = x[v] + d
            dfs(u)
        elif x[u] != x[v] + d:
            return False
    return True

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    L, R, D = map(int, input().split())
    es[L].append((R, D))
    es[R].append((L, -D))
x = [None for i in range(N+1)]
flag = True
for v in range(1, N+1):
    if x[v] == None:
        x[v] = 0
        if dfs(v) == False:
            flag = False
            break
if flag:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    l,r,d=map(int,input().split())
    graph[r-1].append((l-1,-d))
    graph[l-1].append((r-1,d))
INF=10**10
x_list=[INF]*n
import sys
def dfs(x):
    for i in graph[x]:
        if x_list[i[0]]==INF:
            x_list[i[0]]=x_list[x]+i[1]
            dfs(i[0])
        else:
            if x_list[i[0]]==x_list[x]+i[1]:
                pass
            else:
                print('No')
                sys.exit()
for i in range(n):
    if x_list[i]==INF:
        x_list[i]=0
        dfs(i)
print('Yes')