ORIGINAL CODING QUESTION
Cheapest route with a hop limit
Find the cheapest directed route using AT MOST k edges, not k intermediate stops. Return -1 if none qualifies.
Original exercise · hard. Editorial role relevance does not imply a company has asked this question.
Input and output
n m, m triples (u,v,cost), then source target k.
Constraints
1 ≤ n ≤ 30; 0 ≤ m ≤ 100; vertex IDs in [0,n). 0 ≤ cost ≤ 100. 0 ≤ k ≤ n.
Example 1
Input
3 3 0 1 2 1 2 2 0 2 9 0 2 1
Output
9
Only the direct route fits one edge, cost 9.
Example 2
Input
3 3 0 1 2 1 2 2 0 2 9 0 2 2
Output
4
Two edges give cost 4.
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
Track cost after at most each allowed edge count.
Hint 2
Use the previous round when relaxing a new edge.
Hint 3
In-place relaxation can accidentally exceed the hop limit.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →