ORIGINAL CODING QUESTION
Cheapest directed service route
Return the cheapest directed source-to-target route cost, or -1 if unreachable. Source equals target has cost zero.
Original exercise · medium. Editorial role relevance does not imply a company has asked this question.
Input and output
n m, then m triples (u,v,nonnegative cost), then source target.
Constraints
1 ≤ n ≤ 30; 0 ≤ m ≤ 100; vertex IDs in [0,n). 0 ≤ cost ≤ 100.
Example 1
Input
3 3 0 1 5 1 2 2 0 2 10 0 2
Output
7
The indirect route costs 7.
Example 2
Input
3 1 0 1 2 0 2
Output
-1
Target 2 is unreachable.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
Nonnegative costs allow Dijkstra’s ordering.
Hint 2
Relax outgoing edges from the smallest unfinished distance.
Hint 3
Do not confuse hop count with route cost.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →