Funcia
Lv.3floyd-warshallgraphshortest-path

All-Pairs Travel Time

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

There are n cities numbered 0 to n - 1. roads[i] = [a, b, t] is a one-way road from city a to city b taking t minutes.

For each queries[j] = [a, b], find the shortest travel time from a to b and return the answers in query order. Use -1 when b cannot be reached and 0 when a = b.

Examples

nroadsqueriesresult
4[[0, 1, 5], [1, 2, 2], [0, 2, 9], [2, 3, 1]][[0, 2], [0, 3], [3, 0], [1, 1]][7, 8, -1, 0]
3[[0, 1, 4], [1, 0, 1], [0, 1, 2]][[1, 0], [0, 1], [2, 1]][1, 2, -1]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int, roads: int[][], queries: int[][]) → int[]

Constraints

  • 1≤1 \le n ≤200\le 200
  • 0≤0 \le roads.length ≤20,000\le 20{,}000, 0≤0 \le a, b <n< n, 1≤1 \le t ≤106\le 10^6; parallel roads and a = b may appear
  • 1≤Q=1 \le Q = queries.length ≤50,000\le 50{,}000

Expected complexity

Time
O(n^3 + Q)
Space
O(n^2)

Examples

nroadsqueriesExpected
4[[0,1,5],[1,2,2],[0,2,9],[2,3,1]][[0,2],[0,3],[3,0],[1,1]][7,8,-1,0]
3[[0,1,4],[1,0,1],[0,1,2]][[1,0],[0,1],[2,1]][1,2,-1]

Hint

Hint

With only 200 cities, precompute every pair once with Floyd–Warshall (k as the outermost loop, d[i][j] = min(d[i][j], d[i][k] + d[k][j]), keeping the shortest of parallel roads) and answer each query by lookup. Running Dijkstra per query is O(Q⋅Mlog⁡n)O(Q \cdot M \log n) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251332 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.