Cheapest Route to Every Town With Road Tolls
Implement cheapestRoutes
You are given a network of towns connected by two-way roads, each with a positive toll, as a symmetric weight matrix. Starting from one town, find the smallest total toll to every other town, or -1 for towns that cannot be reached.
With only positive tolls, the town with the smallest known toll can never be reached more cheaply later: that is the greedy idea behind Dijkstra's algorithm.
Example 1:
Input: weights = [[0,4,8,0,0,0],[4,0,2,5,0,0],[8,2,0,9,10,0],[0,5,9,0,3,6],[0,0,10,3,0,2],[0,0,0,6,2,0]], src = 0
Output: [0,4,6,9,12,14]
Example 2:
Input: weights = [[0,3],[3,0]], src = 1
Output: [3,0]
Example 3:
Input: weights = [[0,0],[0,0]], src = 0
Output: [0,-1]
+ 14 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 8 towns numbered 0 … n-1; weights is a symmetric n × n matrix: weights[u][v] = 0 means no road between u and v, and weights[u][v] = w (1 ≤ w ≤ 20) means a two-way road with toll w - ●
weights[u][u] = 0; all tolls are positive - ●
0 ≤ src < n is the starting town - ●
Return an array where entry i is the smallest total toll on a route from src to town i, or -1 if town i cannot be reached
weights =
[[0,4,8,0,0,0], [4,0,2,5,0,0], [8,2,0,9,10,0], [0,5,9,0,3,6], [0,0,10,3,0,2], [0,0,0,6,2,0]]
src =
0