Problem p03608 (python)

Fixed submission:
# ABC073D - joisino's travel
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v][u] = G[u][v] = c
    dist = floyd_warshall(G, directed=0)
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC073D - joisino's travel
from heapq import heappop, heappush
from itertools import permutations
from typing import List, Tuple

INF = 1 << 30


def dijkstra(source: int, edges: List[Tuple[int, int]]) -> List[int]:
    """
    Compute the distance of the shortest path from V_source to each vertex.

    Args:
        source: V_source
        edges: Edges info
    Returns:
        dist: A list of distance from V_source
    """
    edges_count = len(edges)
    dist = [INF] * edges_count
    dist[source] = 0
    undetermined = edges_count - 1  # V_0 is determined in 1-idx graph
    queue = [(0, source)]
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        for next_cost, u in edges[v]:
            if cost + next_cost < dist[u]:
                dist[u] = cost + next_cost
                heappush(queue, (dist[u], u))
        undetermined -= 1
        if not undetermined:
            break
    return dist  # There may be no path from V_source to some vertices.


def main():
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    edges = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        edges[v].append((cost, u)), edges[u].append((cost, v))
    dist = {v: dijkstra(v, edges) for v in visit}
    ans = INF
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC073D - joisino's travel (210ms)
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [1 << 60] * size
    unchecked = size - 1  # vertex_0 won't appear in 1-idx graph
    queue = [(0, start)]
    heapify(queue)
    while queue:
        cost, v = heappop(queue)
        if cost > dist[v]:
            continue
        dist[v] = cost
        for next_cost, u in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (cost + next_cost, u))
        unchecked -= 1
        if not unchecked:
        return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, cost in zip(*[iter(ABC)] * 3):
        G[v].append((cost, u)), G[u].append((cost, v))
    dist = {v: dijkstra(G, N + 1, v) for v in visit}
    ans = 1 << 60
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    searched = [0] * size
    dist[start], searched[start] = 0, 1
    queue = G[start]
    heapify(queue)
    while queue:
        v, cost = heappop(queue)
        if searched[v] or cost > dist[v]:
            continue
        dist[v] = cost
        searched[v] = 1
        for u, next_cost in G[v]:
            if cost + next_cost < dist[u]:
                heappush(queue, (u, cost + next_cost))
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v].append((u, c)), G[u].append((v, c))
    dist = [None] + [dijkstra(G, N + 1, i) for i in range(1, N + 1)]
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# ABC073D - joisino's travel
from heapq import heapify, heappop, heappush
from itertools import permutations


def dijkstra(G: "Array[Array[int]]", size: int, start: int) -> list:
    dist = [float("inf")] * size
    searched = [0] * size
    dist[start], searched[start] = 0, 1
    queue = G[start]
    heapify(queue)
    while queue:
        v, cost = heappop(queue)
        if searched[v]:
            continue
        dist[v] = cost
        searched[v] = 1
        for u, next_cost in G[v]:
            heappush(queue, (u, cost + next_cost))
    return dist


def main():
    global G, N
    N, M, R, *RABC = map(int, open(0).read().split())
    visit, ABC = RABC[:R], RABC[R:]
    G = [[] for _ in range(N + 1)]
    for v, u, c in zip(*[iter(ABC)] * 3):
        G[v].append((u, c)), G[u].append((v, c))
    dist = [None] + [dijkstra(G, N + 1, i) for i in range(1, N + 1)]
    ans = float("inf")
    for perm in permutations(visit):
        cur = sum(dist[v][u] for v, u in zip(perm, perm[1:]))
        ans = min(ans, cur)
    print(int(ans))


if __name__ == "__main__":
    main()