Dijkstra Shortest Paths

medium · dijkstra

Given n >= 1 vertices numbered 0..n-1, directed edges [source,destination,weight] with nonnegative integer weights, and a valid source, return a length-n distance list. Use None for unreachable vertices; source has distance 0. Parallel edges, self-loops and zero weights are allowed. Edges are directed, not automatically bidirectional. At most 100 vertices and 1000 edges. Examples (JSON; null means Python None): Input: {"n": 4, "edges": [[0, 1, 4], [0, 2, 1], [2, 1, 1], [1, 3, 2]], "source": 0} Output: [0, 2, 1, 4] Input: {"n": 3, "edges": [[0, 1, 0]], "source": 0} Output: [0, 0, null]

Starter code

def shortest_paths(n: int, edges: list[list[int]], source: int) -> list[int | None]:
    """Return nonnegative weighted shortest distances, including unreachable nodes."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    My solution passed all the tests. All zero of them. I forgot to run them.

  2. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.

  3. The GraderCharacter joke · No posting date

    Your solution is correct. Your variable names are a crime scene.

  4. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.