Application lab in Shortest Paths and Relaxation

Mission

Find a directed non-negative shortest-path distance.

Learning outcome: Apply Dijkstra to non-negative weights

Correctness contract

Invariant: Each stored distance is a discovered path cost, and relaxation only improves it with a valid path.

Required technique: Use adjacency lists, long distances, a min-priority queue, and stale-entry skipping; edge weights are non-negative.

Complexity target: time O((V+E) log V); space O(V+E).

Input and output

Input: V and E, then E directed triples (from, to, weight), then source and target vertices. Whitespace may be spaces or line breaks.

Output: Print the shortest distance as one integer, or INF when the target is unreachable. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• Every edge weight is non-negative.
• Every vertex index is valid.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Use adjacency lists, long distances, a min-priority queue, and stale-entry skipping; edge weights are non-negative.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

4 4 0 1 2 0 2 5 1 2 1 2 3 2 0 3

Sample output

5

Why the sample works: Visible walkthrough for the ordinary non-trivial path. The minimum tentative non-negative distance expands first, stale queue entries are skipped, and cheaper outgoing paths are relaxed. Input `4 4 0 1 2 0 2 5 1 2 1 2 3 2 0 3` therefore produces `5`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: If the popped cost differs from the stored distance, it is stale and should not expand edges.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.