Graph/Dijkstra.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

from heapq import heappush, heappop

def dijkstra(s: int, g: list, INF=10**18) -> list:
    n = len(g)
    dist = [INF] * n
    dist[s] = 0
    q = [(0, s)]
    while q:
        pre = heappop(q)[1]
        for nxt, cost in g[pre]:
            if dist[nxt] < dist[pre] + cost: continue
            dist[nxt] = dist[pre] + cost
            heappush(q, (dist[nxt], nxt))

    return dist


def main():
    n, m = map(int,input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        x, y, cost = map(int,input().split())
        x -= 1
        y -= 1
        g[x].append((y, cost))
        g[y].append((x, cost))

    d = dijkstra(0, g)


if __name__ == "__main__":
    main()

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError