116. 0–1 BFS — Binary Edge Weights
Find the minimum total edge weight from the source to each declared vertex. Some edges are free to traverse and others cost one.
Minimize total cost rather than the number of edges. Return a separate result for unreachable vertices and preserve the graph's directed relationships.
Example 1
Input
n=4, edges=[[0,1,1],[0,2,0],[2,1,0]], source=0
Output
[0,0,0,−1]
Explanation: The zero-cost two-hop route improves vertex one after its initial cost-one discovery.
Example 2
Input
n=3, edges=[[0,1,0],[1,0,0],[1,2,1]], source=0
Output
[0,0,1]
Explanation: Strict relaxation stops the zero cycle from generating repeated equal entries.
Constraints
1 <= n <= 1050 <= edge occurrences <= 2 * 1050 <= vertex label < nedges[i].length == 30 <= source < nweight is 0 or 1
Hints
Hint 1
What two costs can a processed distance d propose?
Hint 2
Zero-cost work belongs before pending d+1 work.
Hint 3
Push strict zero improvements to the front, one improvements to the back, and skip stale stored costs.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Zero detour supersedes a one-cost proposal
4
[[0,1,1],[0,2,0],[2,1,0],[1,2,0]]
0
[0,0,0,-1]