Problem p03450 (python)

Fixed submission:
from collections import deque

def topological_sort(graph: list, n_v: int) -> list:
    # graph[node] = [(cost, to)]
    indegree = [0] * n_v # 各頂点の入次数
    for i in range(n_v):
        for c, v in graph[i]:
            indegree[v] += 1

    cand = deque([i for i in range(n_v) if indegree[i] == 0])
    res = []
    while cand:
        v1 = cand.popleft()
        res.append(v1)
        for c, v2 in graph[v1]:
            indegree[v2] -= 1
            if indegree[v2] == 0:
                cand.append(v2)

    return res




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((d, r))

ts = topological_sort(edges, n)

if len(ts) != n:
    ans = "No"
    # print("Not DAG")
else:
    # DAG
    dist = [-1] * n
    ans = "Yes"
    for i in range(n):
        v = ts[i]
        if dist[v] == -1:
            dist[v] = 0

        for c, u in edges[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + c
            elif dist[u] != dist[v] + c:
                ans = "No"
                break

print(ans)

Buggy submission (verdict: Runtime Error):
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")

Buggy submission (verdict: Runtime Error):
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")

Buggy submission (verdict: Runtime Error):
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")

Buggy submission (verdict: Runtime Error):
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")