This documentation is automatically generated by online-judge-tools/verification-helper
ダイクストラ法です.
$edges[from] = [(to1, cost1), (to2, cost2), …)]$の形式で辺情報を与えてください
inf は十分に大きい値を適当に設定してください
dist = dijkstra(edges, s=0, inf=1 << 60)
import heapq
def dijkstra(edges, s=0, inf=1 << 60):
"""
edges[from] = [(to1, cost1), (to2, cost2), ...)]
"""
n = len(edges)
dist = [inf] * n
dist[s] = 0
hq = [s]
while hq:
tmp = heapq.heappop(hq)
d = tmp // n
pos = tmp - n * d
if dist[pos] < d:
continue
for npos, c in edges[pos]:
if dist[npos] > dist[pos] + c:
dist[npos] = dist[pos] + c
heapq.heappush(hq, npos + n * dist[npos])
return dist
Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
bundled_code = language.bundle(
^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
raise NotImplementedError
NotImplementedError