cpl/graph/dijkstra.py

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

Code

from heapq import heappop, heappush
from typing import List, Tuple

from cpl import INF
from cpl.graph import WeightedAdjList


class Dijkstra:
    def __init__(self, graph: WeightedAdjList, start: int) -> None:
        N = len(graph)
        pq: List[Tuple[int, int]] = []
        heappush(pq, (0, start))

        cost: List[int] = [INF] * N
        cost[start] = 0
        prev: List[int] = [-1] * N
        while pq:
            w, v = heappop(pq)
            if w > cost[v]:
                continue
            for nv, nw in graph[v]:
                if (nc := cost[v] + nw) >= cost[nv]:
                    continue
                cost[nv] = nc
                prev[nv] = v
                heappush(pq, (nc, nv))
        self.cost = cost
        self.prev = prev

    def min_cost(self, goal: int):
        return self.cost[goal]

    def min_cost_path(self, goal: int):
        nd = goal
        path: List[int] = []
        while nd >= 0:
            path.append(nd)
            nd = self.prev[nd]
        return path[::-1]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.2/x64/lib/python3.9/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.9.2/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError