tests/dijkstra_getpath.py

• View this file on GitHub
• Last update: 2025-04-17 21:49:15+09:00
• Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

• libs/dijkstra.py
• libs/get_path.py
• libs/graph.py
• libs/standard_input.py
• libs/utils.py

Code

# competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/shortest_path
from libs.dijkstra import dijkstra
from libs.get_path import getpath
from libs.graph import GraphW
from libs.standard_input import il
from libs.utils import INF

N, M, S, T = il()
G = GraphW(N, dire=True)

for _ in [0] * M:
    a, b, w = il()
    G.new_side(a, b, w)

used, prev = dijkstra(G.all(), S, True)

if used[T] == INF:
    print(-1)
else:
    path = getpath(prev, T)

    print(used[T], len(path) - 1)

    for i in range(len(path) - 1):
        print(path[i], path[i + 1])

Test cases

Env	Name	Status	Elapsed	Memory
Python	almost_line_00	AC	2051 ms	118 MB
Python	almost_line_01	AC	2047 ms	118 MB
Python	almost_line_02	AC	1924 ms	98 MB
Python	example_00	AC	30 ms	12 MB
Python	example_01	AC	30 ms	12 MB
Python	grid_random_00	AC	1770 ms	94 MB
Python	grid_swirl_00	AC	2113 ms	102 MB
Python	line_00	AC	2556 ms	164 MB
Python	max_dense_long_00	AC	1217 ms	77 MB
Python	max_dense_random_00	AC	1207 ms	77 MB
Python	max_dense_random_01	AC	1200 ms	77 MB
Python	max_dense_zero_00	AC	1152 ms	62 MB
Python	max_sparse_random_00	AC	1575 ms	103 MB
Python	max_sparse_random_01	AC	2054 ms	115 MB
Python	max_sparse_random_02	AC	2096 ms	116 MB
Python	max_star_00	AC	2907 ms	176 MB
Python	max_star_01	AC	2951 ms	162 MB
Python	small_00	AC	31 ms	12 MB
Python	small_01	AC	30 ms	12 MB
Python	small_02	AC	31 ms	12 MB
Python	small_03	AC	31 ms	12 MB
Python	small_04	AC	30 ms	12 MB
Python	sparse_random_00	AC	1327 ms	105 MB
Python	sparse_random_01	AC	1359 ms	115 MB
Python	sparse_random_02	AC	1392 ms	76 MB
Python	spfa_killer_00	AC	2475 ms	122 MB
Python	wrong_dijkstra_handmade_00	AC	32 ms	12 MB
Python	wrong_dijkstra_killer_00	AC	2422 ms	136 MB
Python	wrong_dijkstra_killer_01	AC	2565 ms	124 MB

Back to top page