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
mlines:u v w - next
qlines: a queryu 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).