Cheapest Routes Through a One-Way Freight Network
Implement cheapestFromSource
A freight company has n depots connected by one-way routes that never form a cycle. The routes are given as a cost matrix: cost[u][v] is the price of the route from u to v, or 0 if there is no such route. Goods start at the source depot. For every depot, find the cheapest total cost of getting goods there, or -1 if it cannot be reached.
Because there are no cycles, the depots can be processed in topological order and each depot's cost is final when its turn comes.
Example 1:
Input: cost = [[0,4,1,0,0,0],[0,0,0,5,0,0],[0,2,0,8,0,0],[0,0,0,0,3,0],[0,0,0,0,0,0],[0,0,0,0,1,0]], src = 0
Output: [0,3,1,8,11,-1]
Example 2:
Input: cost = [[0,7],[0,0]], src = 0
Output: [0,7]
Example 3:
Input: cost = [[0,7],[0,0]], src = 1
Output: [-1,0]
+ 14 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 depots numbered 0 … n-1; cost is an n × n matrix: cost[u][v] = 0 means there is no route from u to v, and cost[u][v] = w (1 ≤ w ≤ 20) means a one-way route u → v costing w - ●
The routes contain no cycle (the network is a directed acyclic graph); cost[u][u] = 0 - ●
0 ≤ src < n is the depot where the goods start - ●
Return an array where entry i is the cheapest total cost from src to depot i, or -1 if depot i cannot be reached
cost =
src =