Submission #3026264

---

Source Code Expand

#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


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


def main():
    N, M = map(int, input().split())
    m = defaultdict(list)
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        m[L].append((R, D))
        m[R].append((L, -D))

    x = [None] * N
    for k in range(N):
        if x[k] is not None:
            continue

        x[k] = 0
        que = deque()
        que.append(k)
        while len(que) != 0:
            i = que.popleft()

            for j, d in m[i]:
                if x[j] is None:
                    x[j] = x[i] + d
                    que.append(j)
                else:
                    if x[j] != x[i] + d:
                        print(No)
                        return

    print(Yes)


if __name__ == '__main__':
    main()

Submission Info

Judge Result