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: Wrong Answer

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

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



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


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


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

    
    n, m = mi()
    info = []
    for _ in range(m):
        l, r, dist = mi_0()
        dist += 1
        if l > r:
            l, r, dist = r, l, - dist
        info.append([l, r, dist])
    
    info.sort(key=itemgetter(0))

    print('Yes') if no_contradict_p(info) else print('No')



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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



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


    def no_contradict_p(info):
        point_dict = dict()
        for l, r, dist in info:
            if l not in point_dict:
                # 初期位置 0 に配置するとする
                point_dict[l] = 0
            if r not in point_dict:
                point_dict[r] = point_dict[l] + dist
            else:
                if point_dict[r] != point_dict[l] + dist:
                    return False
        return True

    
    n, m = mi()
    info = []
    for _ in range(m):
        l, r, dist = mi()
        if l > r:
            l, r, dist = r, l, - dist
        info.append([l, r, dist])
    
    info.sort(key=itemgetter(0))

    print('Yes') if no_contradict_p(info) else print('No')



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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


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

print("Yes")

Submission status: Wrong Answer

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

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


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

print("Yes")

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        g[L].add((R, D))

    dist = [-1] * N
    for s in range(N):
        if not g[s]: continue  # 他からたどり着く葉なので、始点に採用して距離0としてはいけない
        if ~dist[s]: continue
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, d in g[v]:
                if ~dist[u]:
                    if dist[u] != dist[v] + d:
                        print('No')
                        return
                else:
                    dist[u] = dist[v] + d
                    dq.append(u)
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        L, R, D = map(int, input().split())
        tree[L - 1].append((R - 1, D))
        tree[R - 1].append((L - 1, -D))

    def dfs(v, p):
        for u, d in tree[v]:
            if u == p:
                continue
            elif depth[u] != f_inf:
                if depth[u] != depth[v] + d:
                    print("No")
                    exit()
                else:
                    return
            depth[u] = depth[v] + d
            dfs(u, v)

    depth = [f_inf for _ in range(n)]
    for i in range(n):
        if len(tree[i]) != 0:
            depth[i] = 0
            dfs(i, -1)
            break

    print("Yes")


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    n, m = map(int, input().split())
    if m == 0:
        print("Yes")
        exit()
    else:
        lr = [[0]*3 for _ in range(m)]
        for i in range(m):
            l, r, d = map(int, input().split())
            if l < r:
                lr[i][0] = l
                lr[i][1] = r
                lr[i][2] = d
            else:
                lr[i][0] = r
                lr[i][1] = l
                lr[i][2] = -d
        lr = sorted(lr)
        pos = [float("inf")] * n
        OK = True
        for i in range(len(lr)):
            if i == 0:
                pos[lr[0][0]-1] = 0
                pos[lr[0][1]-1] = lr[0][2]
            else:
                l = lr[i][0]-1
                r = lr[i][1]-1
                d = lr[i][2]
                if pos[l] == float("inf"):
                    if pos[r] != float("inf"):
                        pos[l] = pos[r] - d
                    else:
                        if pos[r]-pos[l] != d:
                            OK = False
                else:
                    if pos[r] == float("inf"):
                        pos[r] = pos[l] + d
                    else:
                        if pos[r]-pos[l] != d:
                            OK = False
        if OK:
            print("Yes")
        else:
            print("No")
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret

    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def dijkstra(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素は(ノード, エッジ長)
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    P ... 最短経路木における親
    '''
    pq = PriorityQueue([])
    P = [None] * N
    D = [float('inf')] * N
    D[s] = 0
    pq.push((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.pop()
        if D[v] < d:  # この辺を扱っても最短距離にならない
            continue  # is_visitedなくてもこれを使うことで最小のものを再び探索するのを防げる
        for to, cost in graph[v]:
            if D[to] > D[v] + cost:  # v周りにおける最短経路の候補の更新
                D[to] = D[v] + cost
                pq.push((D[to], to))
                P[to] = v
    return D, P


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# x0を0に固定したときに各点への最短距離が求められて、それが矛盾しなければ良さそう

N, M = read_ints()
graph = defaultdict(lambda: [])
LRD = []
for _ in range(M):
    l, r, d = read_ints()
    l -= 1
    r -= 1
    LRD.append((l, r, d))
    graph[l].append((r, d))
    graph[r].append((l, d))


D, _ = dijkstra(graph, 0, N)
start = D.index(max(D))
D, _ = dijkstra(graph, start, N)  # 一番左をスタートにしないと行けない #一番遠いノードかな
# すべての入力と矛盾しないか確認
# print(start, D)
for l, r, d in LRD:
    if abs(D[r] - D[l]) != d:
        print('No')
        exit()
print('Yes')

Submission status: Wrong Answer

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

p = [0] * (n+1)

lrd = []
L = 0
R = 1
D = 2

for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l, r, d])
    if p[r] - p[l] != d:
        p[r] += p[l] + d

# print(p)

for l in lrd:
    if p[l[R]] - p[l[L]] != l[D]:
        print("No")
        exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret


    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def dijkstra(graph, s, N):
    '''
    graph...隣接リスト形式 リスト内要素は(ノード, エッジ長)
    s...始点ノード
    N...頂点数

    return
    ----------
    D ... 各点までの最短距離
    P ... 最短経路木における親
    '''
    pq = PriorityQueue([])
    P = [None] * N
    D = [float('inf')] * N
    D[s] = 0
    pq.push((D[s], s))  # (最短距離, 次のノード)
    while pq:
        d, v = pq.pop()
        if D[v] < d:  # この辺を扱っても最短距離にならない
            continue  # is_visitedなくてもこれを使うことで最小のものを再び探索するのを防げる
        for to, cost in graph[v]:
            if D[to] > D[v] + cost:  # v周りにおける最短経路の候補の更新
                D[to] = D[v] + cost
                pq.push((D[to], to))
                P[to] = v
    return D, P


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc087/tasks/arc090_b
# x0を0に固定したときに各点への最短距離が求められて、それが矛盾しなければ良さそう

N, M = read_ints()
graph = defaultdict(lambda: [])
LRD = []
for _ in range(M):
    l, r, d = read_ints()
    l -= 1
    r -= 1
    LRD.append((l, r, d))
    graph[l].append((r, d))
    graph[r].append((l, d))

D, _ = dijkstra(graph, 0, N)
# print(D)
# すべての入力と矛盾しないか確認
for l, r, d in LRD:
    if l > r:
        l, r = r, l
    if D[r] - D[l] != d:
        print('No')
        # print(r, l, D[r], D[l], d)
        exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    L,R=L-1,R-1
    G[L].append((D,R))
    G[R].append((-D,L))
ok=True
que=deque(range(N))
dist=[-1]*N
while que:
    v=que.popleft()
    for cost,nv in G[v]:
        if dist[nv]!=-1:
            if dist[nv]!=dist[v]+cost:
                ok=False
                break
        else:
            dist[nv]=dist[v]+cost
            que.append(nv)
print('Yes' if ok else 'No')

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
dist=[float("inf")]*N
tree=[[] for _ in range(N)]
table=[]
flag=1
for i in range(M):
    l,r,d=map(int,input().split())
    if l<r:
        table.append([l,r,d])
    else:
        table.append([r, l, -d])
table=x=sorted(table,key=lambda x:x[1])
table.sort(key=lambda x:x[0])
#print(table)
#print(tree)
for i in range(M):
    if dist[table[i][0]-1]==float("inf"):
        dist[table[i][0] - 1]=0

    if dist[table[i][1]-1]==float("inf"):
        dist[table[i][1]-1]=dist[table[i][0] - 1]+table[i][2]
    elif dist[table[i][1]-1]!=dist[table[i][0] - 1]+table[i][2]:
        flag=0
        break
    #print(dist)
if flag==1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    redge=[[] for _ in range(N)]
    for _ in range(M):
        l,r,d=map(int1,input().split())
        d+=1
        edge[l].append((r,d))
        redge[r].append((l,d))
    s=0
    rs=0
    D=[-INF]*N
    used=[False]*N
    rused=[False]*N
    f=True
    while f:
        for s in range(s,N):
            if D[s]==-INF:
                break
        else:
            f=False
        D[s]=0
        stack=[s]
        while stack:
            v=stack.pop()
            used[v]=True
            for nv,d in edge[v]:
                if D[nv]==-INF:
                    D[nv]=D[v]+d
                else:
                    if D[nv]!=D[v]+d:
                        print('No')
                        exit()
                if not used[nv]:
                    stack.append(nv)
        for s in range(s,N):
            if D[s]==-INF:
                f=True
                break
        stack=[rs]
        while stack:
            v=stack.pop()
            rused[v]=True
            for nv,d in redge[v]:
                if D[nv]==-INF:
                    D[nv]=D[v]-d
                else:
                    if D[nv]!=D[v]-d:
                        print('No')
                        exit()
                if not rused[nv]:
                    stack.append(nv)
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    redge=[[] for _ in range(N)]
    for _ in range(M):
        l,r,d=map(int1,input().split())
        d+=1
        edge[l].append((r,d))
        redge[r].append((l,d))
    s=0
    D=[-INF]*N
    while True:
        for s in range(s,N):
            if D[s]==-INF:
                break
        else:
            break
        D[s]=0
        stack=[s]
        while stack:
            v=stack.pop()
            for nv,d in edge[v]:
                if D[nv]==-INF:
                    D[nv]=D[v]+d
                    stack.append(nv)
                else:
                    if D[nv]!=D[v]+d:
                        print('No')
                        exit()
        stack=[s]
        while stack:
            v=stack.pop()
            for nv,d in redge[v]:
                if D[nv]==-INF:
                    D[nv]=D[v]-d
                    stack.append(nv)
                else:
                    if D[nv]==D[v]-d:
                        print('No')
                        exit()
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


    dis = [False]*n

    def search(x):

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

if __name__ == "__main__":
    main()