Cheapest Route Between Every Pair of Stations
Implement allPairs
A rail network has n stations and one-way links with positive prices, given as a price matrix. For every ordered pair of stations, find the cheapest total price of a route from the first to the second, or -1 if there is none.
Running a single-source algorithm from every station works, but the Floyd–Warshall algorithm computes the whole table with three nested loops by considering, one after another, each station as a possible middle stop.
Example 1:
Input: roads = [[0,3,0,10,0],[0,0,2,0,0],[4,0,0,1,0],[0,0,0,0,5],[0,1,0,0,0]]
Output: [[0,3,5,6,11],[6,0,2,3,8],[4,7,0,1,6],[12,6,8,0,5],[7,1,3,4,0]]
Example 2:
Input: roads = [[0,5],[0,0]]
Output: [[0,5],[-1,0]]
Example 3:
Input: roads = [[0]]
Output: [[0]]
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 7 stations numbered 0 … n-1; roads is an n × n matrix: roads[u][v] = 0 (u ≠ v) means there is no one-way link from u to v, and roads[u][v] = w (1 ≤ w ≤ 20) means a link costing w - ●
roads[u][u] = 0; all link prices are positive - ●
The cheapest price from a station to itself is 0 - ●
Return an n × n matrix whose entry [i][j] is the cheapest total price of a route from station i to station j, or -1 if station j cannot be reached from i
roads =