Trace lab in Shortest Paths and Relaxation

Mission

Return min(current distance, source distance + edge weight).

Learning outcome: Trace a single relaxation decision

Correctness contract

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

Required technique: Compute the candidate source distance plus edge weight using long arithmetic and keep the smaller valid distance.

Complexity target: time O(1); space O(1).

Input and output

Input: The current source distance, edge weight, and current destination distance. Whitespace may be spaces or line breaks.

Output: Print the single exact numeric result with no label. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• Adding the source distance and edge weight fits in signed 64-bit storage.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Compute the candidate source distance plus edge weight using long arithmetic and keep the smaller valid distance.
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

5 3 20

Sample output

8

Why the sample works: Visible walkthrough for the ordinary non-trivial path. The candidate path is sourceDistance + edgeWeight, and it replaces the current destination only when smaller. Input `5 3 20` therefore produces `8`.

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: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

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.