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: Accepted

Solution code:
n, m = (int(x) for x in input().split())
p = [(i,0) for i in range(n)]

def check(i):
    j, d = p[i]
    if j != i:
        ii, dd = check(j)
        p[i] = (ii, d+dd)
    return p[i]

f = True
for _ in range(m):
    l, r, d = (int(x) for x in input().split())
    l-=1;r-=1
    li, ld = check(l)
    ri, rd = check(r)
    if li != ri:
        t = d+ld-rd
        if t >= 0:
            p[ri] = (li, t)
        else:
            p[li] = (ri, -t)
    else:
        if rd - ld != d:
            f = False
            break
print("Yes" if f else "No")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(1000000)

N, M = map(int, sys.stdin.readline().split())
E = defaultdict(list)

for _ in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    l -= 1
    r -= 1
    E[l].append((r, d))
    E[r].append((l, -d))

xs = [None] * N

def dfs(i, x):
    xs[i] = x
    mi, ma = x, x
    for j, d in E[i]:
        if xs[j] is None:
            res = dfs(j, x + d)
            if res is None:
                return None
            else:
                mi2, ma2 = res
                mi = min(mi2, mi)
                ma = max(ma2, ma)
        else:
            if xs[j] - x != d:
                return None
    return mi, ma

for i in range(N):
    if xs[i] is None:
        res = dfs(i, 0)
        if res is None:
            break
        else:
            mi, ma = res
            if ma - mi > 1e9:
                break
else:
    print('Yes')
    sys.exit()
print('No')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if checked[j]:
            continue
        if j not in xs:
            xs[j] = xi + d
        elif xi + d != xs[j]:
            return False
        children.add(j)
    checked[i] = True
    for j in children:
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            mn, mx = min(xs.values()), max(xs.values())
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)
INF = 10**10

(N, M) = reads()

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

for _ in range(M):
    (L, R, D) = reads()
    (L, R) = (L-1, R-1)
    edges[L].append((R, D))
    edges[R].append((L, -D))

visited = [False] * N
place = [None] * N

def walk(i):
    if visited[i]:
        return (place[i], place[i])
    visited[i] = True
    (m, M) = (INF, -INF)
    for (j, d) in edges[i]:
        if visited[j] and place[j] != place[i] + d:
            # print("v = ", visited)
            # print("p = ", place)
            print("No")
            exit()
        place[j] = place[i] + d
        (x, y) = walk(j)
        (m, M) = (min(m, x), max(M, y))
    return (m, M)

for i in range(N):
    if not visited[i]:
        place[i] = 0
        (m, M) = walk(i)
        if M - m > 10**9:
            # print("(m, M) = ", (m, M))
            print("No")
            exit()

print("Yes")

Submission status: Accepted

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

from collections import defaultdict
E = [list() for _ in range(N)]

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

locations = [None]*N

for s in range(N):
  if locations[s] is None:
    locations[s] = 0
    stack = [s]

    while stack:
      v = stack.pop()
      p = locations[v]

      for u,d in E[v]:
        if locations[u] is None:
          locations[u] = p+d
          stack.append(u)
        elif locations[u] != p+d:
          print('No')
          exit()


print('Yes')

Submission status: Accepted

Solution code:
import heapq

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[l-1].append((r-1,d))
    graph[r-1].append((l-1,-d))


visited = [False for i in range(n)]
pos = [0 for i in range(n)]

for i in range(n):
    if visited[i]:
        continue
    hq = [(i, 0)]
    while hq:
        v, p = heapq.heappop(hq)
        if visited[v]:
            if p != pos[v]:
                print("No")
                exit()
            continue
        visited[v] = True
        pos[v] = p
        for nv, d in graph[v]:
            if visited[nv]:
                if pos[nv] != p + d:
                    print('No')
                    exit()
                continue
            heapq.heappush(hq, (nv, p+d))
print('Yes')

Submission status: Accepted

Solution code:
# D
from collections import deque
N, M = map(int, input().split())

value_list = [0]*N
done_list = [-1]*N
# -1:any, 0:not_done, 1:done

res = 'Yes'

G = dict()
for i in range(N):
    G[i] = dict()
    
# input
for _ in range(M):
    L, R, D = map(int, input().split())
    G[L-1][R-1] = D
    G[R-1][L-1] = -D
    done_list[L-1] = 0
    done_list[R-1] = 0

# pick one node not resolved
pick = 0

while pick < N and res == 'Yes':
    
    queue = deque([pick])
    done_list[pick] = 1
    value_list[pick] = 0
    
    # BFS
    while len(queue) > 0:
        L = queue.popleft()
        for R in G[L].keys():
            if done_list[R] == 0:
                done_list[R] = 1
                value_list[R] = value_list[L] + G[L][R]
                queue.append(R)
            else:
                if value_list[R] != value_list[L] + G[L][R]:
                    res = 'No'

    # next seed
    while pick < N:
        if done_list[pick] == 0:
            break
        pick += 1
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200002)

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

bio = [None for i in range(n)]
def dfs(x):
    for y, d in a[x]:
        if bio[y] is None:
            bio[y] = bio[x] + d
            if not dfs(y):
                return False
        elif bio[y] != bio[x] + d:
            return False
    return True

for i in range(n):
    if bio[i] is None:
        bio[i] = 0
        if not dfs(i):
            print('No')
            exit(0)
print('Yes')

Submission status: Runtime Error

Solution code:
print(Yes)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n)]
diff = [0]*n

def find(x):
    if par[x] == x:
        return x, 0
    else:
        a, b = find(par[x])
        par[x] = a
        diff[x] += b
        return a, diff[x]


def unite(x,y,z):
    s, ws = find(x)
    t, wt = find(y)
    #print(ws, wt)
    if s==t:
        if ws - wt == z:
            pass
        else:
            print('No')
            exit(0)
    else:
        par[s] = t
        diff[s] = z

unites =[]
for _ in range(m):
    l,r,d = map(int, input().split())
    unites.append((l,r,d))
    unite(l-1,r-1,d)
for x, y, z in unites:
    unites(x-1, y-1, d)

print('Yes')

Submission status: Runtime Error

Solution code:
def f(hito, zahyo, mae=0):
  x[hito]=zahyo
  for tsugi in links[hito]:
    if tsugi[0]==mae:
      continue
      
    if x[tsugi[0]]==None:
      f(tsugi[0], zahyo+tsugi[1], hito)
    else:
      if x[tsugi[0]]==zahyo+tsugi[1]:
        pass
      else:
        print('No')
        exit()

N, M=map(int, input().split())
links=[[] for _ in range(N+1)]
for _ in range(M):
  l, r, d=map(int, input().split())
  links[l].append([r, d])
  links[r].append([l, -d])
  
x=[None]*(N+1)
for i in range(1, N+1):
  if x[i]==None:
    f(i, 0)
    
print('Yes')

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque, defaultdict
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    ref = defaultdict(list)
    sta = 0

    for i in range(m):
        a, b, k = map(int, input().split())
        if i == 0:
            sta = a
        g[a].append(b)
        g[b].append(a)
        ref[(a, b)] = k

    q = deque([sta])
    visited = set()
    dist = [0] * (n + 1)
    dist[sta] = 1

    while q:
        v = q.pop()
        visited.add(v)
        for x in g[v]:
            if x not in visited:
                if ref[(v, x)]:
                    y = ref[(v, x)]
                    if not dist[x]:
                        dist[x] = dist[v] + y
                    elif not dist[v]:
                        dist[v] = dist[x] - y
                    elif dist[x] != dist[v] + y:
                        print("No")
                        exit()
                else:
                    y = ref[(x, v)]
                    if not dist[v]:
                        dist[v] = dist[x] + y
                    elif not dist[x]:
                        dist[x] = dist[v] - y
                    elif dist[v] != dist[x] + y:
                        print("No")
                        exit()
                q.append(x)
    print("Yes")
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# 参考: https://qiita.com/y-tsutsu/items/aa7e8e809d6ac167d6a1

from heapq import heappush, heappop


# 多次元配列
# dp = [[0] * 3 for _ in range(5)


class Edge:
    def __init__(self, to: int, cost: int):
        self._to = to
        self._cost = cost

    @property
    def to(self):
        return self._to

    @property
    def cost(self):
        return self._cost


class Edges(list):
    def __init__(self):
        list.__init__(self)


INF = 1 << 28
MOD = int(1e9) + 7


def dijkstra(graph, s: int):
    n = len(graph)
    dist = [INF for _ in range(n)]
    cnts = [0 for _ in range(n)]

    pq = []
    heappush(pq, (0, s))
    dist[s] = 0
    cnts[s] = 1

    while pq:
        (cost, cur) = heappop(pq)

        if dist[cur] != cost:
            continue

        for next in graph[cur]:
            if dist[next.to] > cost + next.cost:
                heappush(pq, (cost + next.cost, next.to))
                dist[next.to] = cost + next.cost
                cnts[next.to] = cnts[cur]
            elif dist[next.to] == cost + next.cost:
                cnts[next.to] = (cnts[next.to] + cnts[cur]) % MOD

    return dist, cnts


# 入力を受け取る
n, m = map(int, input().split())

s, t = map(lambda i: int(i) - 1, input().split())

g = [Edges() for _ in range(n)]

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

dst1, cnt1 = dijkstra(g, s)
dst2, cnt2 = dijkstra(g, t)

ret = cnt1[t] * cnt1[t] % MOD

for i in range(n):
    if 2 * dst1[i] == dst1[t]:
        sub = cnt1[i] * cnt1[i] % MOD
        sub = sub * cnt2[i] % MOD * cnt2[i] % MOD
        ret = (ret + MOD - sub) % MOD

sum_sub = 0
for u in range(n):
    for e in g[u]:
        v, d = e.to, e.cost
        if 2 * dst1[u] < dst1[t] < 2 * dst1[v] and dst1[u] + d == dst1[v] and dst2[v] + d == dst2[u]:
            sub = cnt1[u] * cnt1[u] % MOD
            sub = sub * cnt2[v] % MOD * cnt2[v] % MOD
            sum_sub = (sum_sub + sub) % MOD

ret = (ret + MOD - sum_sub) % MOD
print(ret)

Submission status: Runtime Error

Solution code:
import sys

def func(array, arr, d):
  for v in arr:
    if array[v[0]] == None:
      d1 = d + v[1]
      array[v[0]] = d1
      arr1 = dic.get(v[0], [])
      
      if not func(array, arr1, d1):
        return False
      
    elif array[v[0]] != d + v[1]:
      return False
    
  return True
      

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

array = [None] * n
dic = {}

for i in range(m):
  l,r,d = map(int, input().split())
  l -= 1
  r -= 1
  
  dic.setdefault(l,[])
  dic.setdefault(r,[])
  dic[l].append((r,d))
  dic[r].append((l,-d))
  
for i in range(n):
  if array[i] != None:
    continue
    
  array[i] = 0
  arr = dic.get(i, [])
  
  if not func(array, arr, 0):
    print('No')
    sys.exit()

print('Yes')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        #dist[x]はxとその親との間の距離を保持している
        self.dist = [0]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            a = self.parents[x]
            self.parents[x]=self.find(self.parents[x])
            self.dist[x] += self.dist[a]
            return self.parents[x]
    def unite(self,l,r,d):
        rRoot = self.find(r)
        lRoot = self.find(l)
        if rRoot == lRoot:
            if self.dist[l] - self.dist[r] != d:
                print("No")
                exit()
        else:
            #rRootとlRoot、どちらが親になるべきか決める
            newLDist = d + self.dist[r]
            if newLDist>=self.dist[l]:
                self.parents[lRoot] = rRoot
                self.dist[lRoot] = newLDist-self.dist[l]
            else:
                self.parents[rRoot] = LRoot
                self.dist[rRoot] = self.dist[l]-newLDist

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000000)
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        #dist[x]はxとその親との間の距離を保持している
        self.dist = [0]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            a = self.parents[x]
            self.parents[x]=self.find(self.parents[x])
            self.dist[x] += self.dist[a]
            return self.parents[x]
    def unite(self,l,r,d):
        rRoot = self.find(r)
        lRoot = self.find(l)
        if rRoot == lRoot:
            if self.dist[l] - self.dist[r] != d:
                print("No")
                exit()
        else:
            #rRootとlRoot、どちらが親になるべきか決める
            newLDist = d + self.dist[r]
            if newLDist>=self.dist[l]:
                self.parents[lRoot] = rRoot
                self.dist[lRoot] = newLDist-self.dist[l]
            else:
                self.parents[rRoot] = LRoot
                self.dist[rRoot] = self.dist[l]-newLDist

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        #dist[x]はxとその親との間の距離を保持している
        self.dist = [0]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            a = self.parents[x]
            self.parents[x]=self.find(self.parents[x])
            self.dist[x] += self.dist[a]
            return self.parents[x]
    def unite(self,l,r,d):
        rRoot = self.find(r)
        lRoot = self.find(l)
        if rRoot == lRoot:
            if self.dist[l] - self.dist[r] != d:
                print("No")
                exit()
        else:
            #rRootとlRoot、どちらが親になるべきか決める
            newLDist = d + self.dist[r]
            if newLDist>=self.dist[l]:
                self.parents[lRoot] = rRoot
                self.dist[lRoot] = newLDist-self.dist[l]
            else:
                self.parents[rRoot] = LRoot
                self.dist[rRoot] = self.dist[l]-newLDist

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    tree.unite(l,r,d)
print("Yes")

Submission status: Runtime Error

Solution code:
class WeightedUnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        # 親ノードとの重み
        self.diff_weight = [0 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        # 親ノードはまだ上書きしない
        root = self.find(self.par[x])
        self.diff_weight[x] += self.diff_weight[self.par[x]]
        self.par[x] = root
        return self.par[x]

    def weight(self, x):
        """ x 根に対する重みを返す """
        self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        """ x と y の差分をとる """
        return self.weight(y) - self.weight(x)

    def unite(self, x, y, w):
        """ ノード x の下にノード y をつける。辺の重みは、w """
        # ただし、実際には、x の根と y の 根をくっつけるので、補正
        w += self.weight(x); w -= self.weight(y)
        x = self.find(x); y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            # y の下に x をつけることになるので、重さは反転させる
            self.par[x] = y
            w = -w
            self.diff_weight[x] = w
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
            self.diff_weight[y] = w
        else:
            self.par[y] = x
            self.rank[x] += 1
            self.diff_weight[y] = w
            
N, M = map(int, input().split())
UF = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    # これまでに入力されたものと等しくないか確認する
    if UF.find(L) == UF.find(R):
        if UF.diff(L, R) != d:
            print('No')
            break
    else:
        UF.unite(L, R, D)
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
#!python3

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


def judge(W, D, visit, i):
    visit[i] = True
    for j, d in W[i]:
        if D[j] is None:
            D[j] = D[i] + d
        else:
            if D[i] + d != D[j]:
                return True
        if visit[j]:
            continue
        if judge(W, D, visit, j):
            return True
    
    return False


def main():
    W = [[] for _ in range(N)]
    for l, r, d in LRD:
        W[l - 1].append((r - 1, d))
        W[r - 1].append((l - 1, -d))
    
    D = [None] * N
    visit = [False] * N
    for i in range(N):
        if visit[i]:
            continue
        D[i] = 0
        if judge(W, D, visit, i):
            print("No")
            return
    
    print("Yes")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
indeg=[0]*n
touch=[0]*n
for _ in range(m):
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    touch[l]=1
    touch[r]=1
    g[l].append((r,d))
    indeg[r]+=1
if m==0:
    print('Yes')
    exit()
entered=False
for i in range(n):
    if indeg[i]==0 and touch[i]==1:
        vis=[False]*n
        entered=True
        dist=[-1]*n
        dist[i]=0
        def dfs(u):
            vis[u]=1
            for v,wt in g[u]:
                if dist[v]==-1:
                    dist[v]=dist[u]+wt
                elif dist[v]!=dist[u]+wt:
                    print('No')
                    exit()
                if vis[v]==False:
                    dfs(v)
        dfs(i)

if entered==False:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/arc090/tasks/arc090_b

class Edge:
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost


N, M = map(int, input().split())
visited = [False for _ in range(N + 1)]
edges = dict()
dist = [0 for _ in range(N + 1)]

for _ in range(M):
    L, R, D = map(int, input().split())

    edges[L] = edges.get(L, [])
    edges[L].append(Edge(R, D))

    edges[R] = edges.get(R, [])
    edges[R].append(Edge(L, -D))


def bfs(v, d):
    if visited[v]:
        return dist[v] == d

    dist[v] = d
    visited[v] = True
    for e in edges.get(v, []):
        if not bfs(e.v, e.cost + d):
            return False

    return True


for i in range(1, N + 1):
    if visited[i]:
        continue
    dist[i] = 0
    if not bfs(i, 0):
        print('No')
        exit(0)

print('Yes')

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/arc090/tasks/arc090_b

class Edge:
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost


N, M = map(int, input().split())
visited = [False for _ in range(N + 1)]
edges = dict()
dist = dict()

for _ in range(M):
    L, R, D = map(int, input().split())

    edges[L] = edges.get(L, [])
    edges[L].append(Edge(R, D))

    edges[R] = edges.get(R, [])
    edges[R].append(Edge(L, -D))


def bfs(v, d):
    if visited[v]:
        return dist[v] == d

    dist[v] = d
    visited[v] = True
    for e in edges.get(v, []):
        if not bfs(e.v, e.cost + d):
            return False

    return True


for i in range(1, N + 1):
    if visited[i]:
        continue
    dist[i] = 0
    if not bfs(i, 0):
        print('No')
        exit(1)

print('Yes')

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/arc090/tasks/arc090_b

class Edge:
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost


N, M = map(int, input().split())
visited = [False for _ in range(N + 1)]
edges = dict()
dist = dict()

for _ in range(M):
    L, R, D = map(int, input().split())

    edges[L] = edges.get(L, [])
    edges[L].append(Edge(R, D))
    edges[R] = edges.get(R, [])
    edges[R].append(Edge(L, -D))


def bfs(v, d) -> bool:
    if visited[v]:
        return dist[v] == d

    dist[v] = d
    visited[v] = True
    for e in edges.get(v, []):
        if not bfs(e.v, e.cost + d):
            return False

    return True


for i in range(1, N + 1):
    if visited[i]:
        continue
    dist[i] = 0
    if not bfs(i, 0):
        print('No')
        exit(0)

print('Yes')

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
    n,m=map(int,input().split())
    g=[[] for i in range(n)]
    for i in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        g[a].append([b,c])
        g[b].append([a,-c])
    inf=10**10
    v=[inf]*n
    while max(v)==inf:
        s=v.index(inf)
        q=deque([s])
        v[s]=0
        while q:
            p=q.pop_left()
            for i in g[p]:
                if v[i[0]]==inf:
                    v[i[0]]=v[p]+i[1]
                    q.append(i[0])
                else:
                    if v[i[0]]!=v[p]+i[1]:
                        return 'No'
    return 'Yes'
                            
  
print(main())

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
    n,m=map(int,input().split())
    g=[[] for i in range(n)]
    for i in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        g[a].append([b,c])
        g[b].append([a,-c])
    inf=10**10
    v=[inf]*n
    while max(v)==inf:
        s=v.index(inf)
        q=deque([s])
        v[s]=0
        while q:
            p=q.pop_left()
            for i in g[p]:
                if v[i[0]]==inf:
                    v[i[0]]=v[p]+i[1]
                    p.append(i[0])
                else:
                    if v[i[0]]!=v[p]+i[1]:
                        return 'No'
    return 'Yes'
                            
  
print(main())

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
L = [deque([]) for _ in range(N)]

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

D = [0] * N
F = [False] * N

def dfs(n, d):
    if F[n-1]:
        if D[n-1] == d:
            return True
        else:
            return False
    F[n-1] = True
    D[n-1] = d
    for nn, d_ in L[n-1]:
        if not dfs(nn, d+d_):
            return False
    else:
        return True

for n in range(1, N+1):
    if not dfs(n, D[n-1]):
        print('No')
        exit()
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
vs = set()
def dfs_w(d, stack):
    depthh = [-1] + [0]*N
    pvs = set()
    if stack[0] in vs:
        return True
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)

        for u, dpd in d[v]:
            if u in pvs:
                if depthh[u] != depthh[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack += [(u, dpd)]

    return True
#    return S, F, depth, depthh

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")

Submission status: Runtime Error

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

def bfs(graph, start):
    while graph != {}:
        start = min(graph.keys())
        queue = deque([])
        queue.append(start)
        pos = {}
        pos[start] = 0

        while queue:
            u = queue.popleft()
            if u not in graph:
                continue
            for v,d in graph[u].items():
                if v not in pos:
                    pos[v] = pos[u] + d
                    queue.append(v)
                elif pos[v] != pos[u] + d:
                    return False
            del graph[u]
            # print(queue)
        return True

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

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

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

def bfs(graph, start):
    queue = deque([])
    queue.append(start)
    pos = {}
    pos[start] = 0

    while queue:
        u = queue.popleft()
        if u not in graph:
            if graph != {}
                u = min(graph.keys())
                pos = {u:0}
            else:
                continue
        for v,d in graph[u].items():
            if v not in pos:
                pos[v] = pos[u] + d
                queue.append(v)
            elif pos[v] != pos[u] + d:
                return False
        del graph[u]
        # print(queue)
    return True

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

graph = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in graph:
        graph[r] = {}
    graph[r][l] = -d

if m == 0 or bfs(graph, min(graph.keys())):
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

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

def bfs(graph, out, start):
    queue = deque([])
    queue.append(start)
    pos[start] = 0
    dis = {0:start}
    mx = 0
    mn = 0
    mod = 10**9

    while queue:
        u = queue.popleft()
        if u not in graph:
            if graph != {}:
                u = min(graph.keys())
            else:
                continue
        for v,d in graph[u].items():
            if v not in pos:
                pos[v] = pos[u] + d
                dis[pos[u] + d] = v
                queue.append(v)
                if pos[v]> mx:
                    mx = pos[v]
                    if mx - mn > mod:
                        return False
            elif pos[v] != pos[u] + d:
                return False
        del graph[u]
        if u not in out:
            continue
        for v,d in out[u].items():
            if v not in pos:
                pos[v] = pos[u] + v
                queue.append(v)
                if pos[v] < mn:
                    mn = pos[v]
                    if mx - mn > mod:
                        return False
            elif pos[v] != pos[u] + d:
                return False
        # print(queue)
    return True

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

graph = {}
out = {}
for i in range(m):
    l,r,d = map(int, input().split())
    if l not in graph:
        graph[l] = {}
    graph[l][r] = d
    if r not in out:
        out[r] = {}
    out[r][l] = -d

pos = {}
if m == 0 or bfs(graph, out, min(graph.keys())):
    print('Yes')
else:
    print('No')

# print(graph)
# print(pos)