Skills101
← All coding problems

All-Pairs Shortest Paths (Floyd-Warshall)

mediumGraphs II+20 XPTime limit 3s

A delivery company has n hubs and m one-way roads u v w with travel cost w. Some roads carry a subsidy, so w can be negative — but no loop of roads has a negative total. Answer q questions: what is the cheapest cost from hub u to hub v?

Input:

  • line 1: n m q
  • next m lines: u v w
  • next q lines: a query u v

Output: one line per query: the minimum cost, 0 when u = v, or INF if v cannot be reached from u.

Constraints: 1 ≤ n ≤ 150, 0 ≤ m ≤ 5000, 1 ≤ q ≤ 10⁴, −10⁴ ≤ w ≤ 10⁴, u ≠ v for roads; several roads may join the same pair. There is no negative cycle.

Think about it: with many queries, compute all distances once. Floyd-Warshall: for every middle hub k, for every pair (i, j), try dist[i][k] + dist[k][j]. The k loop must be the outermost. O(n³), and it handles negative edges. Careful: never add to an "infinity" value.

Sample input 1

4 5 3
1 2 3
2 3 -2
1 3 4
3 4 2
4 1 1
1 3
4 2
3 2

Sample output 1

1
4
6

Sample input 2

2 0 2
1 2
2 2

Sample output 2

INF
0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.