A delivery drone network connects n relay hubs, numbered 0 to n - 1. There are m
one-way relay links; a link from hub u to hub v costs w units of battery to traverse. The drone
always launches from hub 0 and must reach a designated base hub. Multiple links between the same
pair of hubs may exist (with different costs), and a link never connects a hub to itself.
Print the minimum total battery cost to travel from hub 0 to the base hub, moving only along the
directed links. If the base hub cannot be reached from hub 0, print -1 instead.
Line 1: two integers n m.
Next m lines: three integers u v w -- a directed link from hub u to hub v costing w battery
units (hubs are 0-indexed).
Last line: one integer, the index of the base hub.
A single integer: the minimum total cost from hub 0 to the base hub, or -1 if it is unreachable.
Example 1
Input
4 4 0 1 4 0 2 1 2 1 1 1 3 1 3
Expected
3
Explanation
The cheapest way to reach base 3 is 0 -> 2 -> 1 -> 3 costing 1+1+1=3, which beats the direct-ish 0 -> 1 -> 3 costing 4+1=5.
Example 2
Input
3 1 0 1 5 2
Expected
-1
Explanation
There is no link leading to hub 2 at all, so it can never be reached and the answer is -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 →