A courier network is a weighted undirected graph of n stations (numbered 0 to n-1) connected by roads, each with a positive integer travel cost usable in both directions.
A delivery must start at station s, end at station t, and pass through a mandatory checkpoint station r at some point along the way (the order of stations otherwise being free, and stations may be revisited). Find the minimum possible total travel cost of such a trip, or report that it is impossible.
Because all costs are positive, the cheapest trip through r costs exactly the shortest-path distance from s to r plus the shortest-path distance from r to t.
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a two-way road between u and v with cost w.
Final line: three integers s r t (start, required checkpoint, target).
A single integer: the minimum total cost of a trip from s to t passing through r, or -1 if no such trip exists.
Example 1
Input
5 6 0 1 2 1 2 2 0 3 1 3 4 1 4 2 1 0 2 1 0 1 2
Expected
4
Explanation
Forced through checkpoint 1: dist(0,1)=2 and dist(1,2)=2, so the minimum cost is 4 — even though 0->2 directly costs only 1, the checkpoint must be visited.
Example 2
Input
3 1 0 1 5 0 2 1
Expected
-1
Explanation
The checkpoint is station 2, but station 2 has no roads, so it can never be reached from start 0: the trip is impossible (-1).
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →