Challenge lab in Shortest Paths and Relaxation

Mission

Find a directed shortest path when edges may be negative.

Learning outcome: Handle negative edges with Bellman-Ford

Correctness contract

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

Required technique: Relax all directed edges for up to V - 1 passes while guarding unreachable sources.

Complexity target: time O(VE); 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:

• No negative cycle is reachable from the source.
• 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: Relax all directed edges for up to V - 1 passes while guarding unreachable sources.
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 1 1 2 -2 2 3 3 0 3 10 0 3

Sample output

2

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Repeated full-edge relaxation propagates valid improvements across paths containing up to V - 1 edges. Input `4 4 0 1 1 1 2 -2 2 3 3 0 3 10 0 3` therefore produces `2`.

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: A complete pass with no updates means all reachable shortest distances are already stable.

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.