Given a small weighted graph and many distance queries, return the shortest path distance between the requested city pairs. Pattern focus: Floyd-Warshall. This is a clean all-pairs shortest path query problem.
n = city count, edges = weighted roads, queries = list of city pairs
array of shortest distances for each query
Example 1:
Input:
n = 3 edges = [[0,1,4],[1,2,6],[0,2,15]] queries = [[0,2],[2,0],[0,1]]
Output:
[10,10,4]
Explanation:
The indirect route 0 -> 1 -> 2 is cheaper than the direct road.
Example 2:
Input:
n = 3 edges = [[0,1,2]] queries = [[0,2],[1,0]]
Output:
[-1,2]
Explanation:
Unreachable pairs become -1.
Example 3:
Input:
n = 2 edges = [[0,1,9]] queries = [[0,1],[1,0]]
Output:
[9,9]
Explanation:
An undirected road has the same distance in both directions.