Minimum Cost With a Mandatory Checkpoint

Advanced0-1 BFS practice · C++17Best score: not submitted

Client-side educational grading. Submit runs your C++17 program against ten predefined tests in your browser. Tests are intentionally visible through See Hidden Tests. Scores are local practice records, not secure competition results.

main.cpp · C++17

Loading Monaco Editor…

Loading this problem’s draft…

Custom Input

Ctrl / ⌘ + Enter runs your custom test. Input limit: 1 MiB.

Loading editor…

Standard Output

Standard Error

Compiler Diagnostics

Submission results

Ten tests, ten points each. Output is checked against the expected answer. Custom runs never change your score.

Each test has a 5-second execution limit, 256 MiB linked program WASM memory maximum, and 1 MiB combined output limit. Allocated WASM memory is not peak browser memory. Deep recursion can overflow the WASM stack; an iterative traversal is safer for long paths.

Problem statement

You are given a directed graph with N vertices and M edges. Each edge has a cost of either 0 or 1. You must travel from S to T while visiting K at least once. Find the minimum total cost of such a route. Vertices and edges may be visited multiple times. If no valid route exists, print -1. Self-loops and repeated edges are allowed.

Input format

First line: N M. Next M lines: U V W. Last line: S K T.

Output format

Print the minimum total cost, or -1.

Constraints

1 ≤ N ≤ 100000
0 ≤ M ≤ 200000
1 ≤ U, V, S, K, T ≤ N
W is either 0 or 1.

Sample input

Sample output

Sample explanation

Reach checkpoint 3 by 1 → 2 → 3 at cost 1, then take 3 → 5 at cost 0. The cheaper direct route through 2 → 5 does not visit the checkpoint.

Need a hint?

Run 0-1 BFS from S and from K. Answer = dist(S,K) + dist(K,T). Expected complexity: O(N + M).

Review 0-1 BFS →