seekworser's Library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by seekworser Hosted on GitHub Pages — Theme by mattgraham

competitive/python/dijkstra.py

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

Code

from heapq import heappush, heappop
from math import inf

N, M = map(int, input().split())

G = [[] for _ in range(N)]
for _ in range(M):
  a, b, c = map(int, input().split())
  G[a-1].append((b-1, c))
  G[b-1].append((a-1, c))

f_to = [inf for _ in range(N)]
to_N = [inf for _ in range(N)]

h = [(0, 0)]
f_to[0] = 0
while h:
  c, n = heappop(h)
  for nn, cn in G[n]:
    if f_to[nn] > c + cn:
      f_to[nn] = c + cn
      heappush(h, (c + cn, nn))

h = [(0, N-1)]
to_N[N-1] = 0
while h:
  c, n = heappop(h)
  for nn, cn in G[n]:
    if to_N[nn] > c + cn:
      to_N[nn] = c + cn
      heappush(h, (c + cn, nn))

for i in range(N):
  print(f_to[i] + to_N[i])

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

Back to top page