Practice arena
C++17·2 s·128 MB
GraphsIntermediate
Shortest weighted routes
Compute the shortest distance from a source to every vertex in an undirected graph with non-negative edge weights. Print -1 for unreachable vertices.
Input
- — The first line contains T.
- — Each case starts with n, m, and source, followed by m edges u v w.
Output
Print n distances in vertex order for each graph, using -1 when unreachable.
Technique
min heap + stale-entry rejection
Target
O((V+E) log V)
Constraints & sample
- 1 ≤ n ≤ 200,000
- 0 ≤ m ≤ 300,000
- 0 ≤ w ≤ 10⁹
- Distances require 64-bit integers
Sample input
2 5 6 0 0 1 4 0 2 1 2 1 2 1 3 1 2 3 5 3 4 3 3 1 2 0 1 5
Expected output
0 3 1 4 7 -1 -1 0
Before you submit
- Test the smallest valid input and one awkward edge case.
- Keep the solution within O((V+E) log V).
- Match spacing and line breaks exactly before checking 7 hidden cases.
Draft saved locally · 848 / 30,000
Ln 1, Col 1Spaces: 4UTF-8LFC++17
Visible testcases
Editable and stored only in this browser. Hidden judge cases never change.
Checking your session…
Run checks Sample · Submit checks 7 hidden cases
Run the sample first, then send your solution through 7 hidden cases.
Code runs in an isolated Judge0 environment. Drafts and custom visible cases stay on this device; submission metadata and progress sync to MongoDB.