1666. Routes Between Many Pairs
A DIRECTED graph has n vertices and m arrows, every weight at least 1.
Then q questions arrive, each a pair s t. For each, print the vertices of a
cheapest route from s to t, or -1 if there is none.
Among all cheapest routes, print the one whose sequence of vertex numbers is
smallest in dictionary order. When s equals t the answer is the single number
s.
3 vertices, 1 -> 2 (4), 2 -> 3 (1), 1 -> 3 (10)
1 3 -> 1 2 3 the detour costs 5 against the direct 10
3 1 -> -1 the arrows do not come back
2 2 -> 2
Problem 1642 prints the DISTANCE between every pair. This prints the routes, and that is a different data structure: a matrix of numbers is not enough to walk along.
## The four things that have to be said
directed? yes, and the questions are ordered pairs, so s to t and t to
s are different questions with different answers.
self-loops? allowed, and never on a cheapest route, since weights are at
least 1.
parallel arrows? allowed, at different weights, and the cheaper copy wins.
unreachable? yes, per question. Print -1 on that question's line only; the
other questions still get their answers. When n is 1 the only
possible question is 1 1, answered 1.
## What most people try first
Floyd-Warshall for the distances, then trying to read a route out of the
distance matrix by looking for any k with d[s][k] + d[k][t] == d[s][t]. That
finds a vertex ON a cheapest route but not the next STEP, so it has to recurse
on both halves, and the dictionary rule becomes very hard to state over a
recursion that splits in the middle rather than walking forwards.
The clean version of that idea is a next-hop matrix: alongside d[i][j], keep
nxt[i][j], the first vertex after i on the chosen route. Then a route is a
walk. Getting the dictionary rule right still needs care, because Floyd-Warshall
updates nxt in an order that has nothing to do with vertex numbers.
## Distances TO each target, then walk forwards
With q at 200 and n at 200 there is a simpler correct answer. For each
question, run Dijkstra on the REVERSED graph from t, giving distT[v], the
cheapest cost from v to t. Then walk forwards from s:
u = s, print u
while u != t:
among arrows (u, v, w) with w + distT[v] == distT[u], take the SMALLEST v
print v, u = v
That is q searches of O(m log n), which is 200 * 5000 * log 200, about
10^7 operations. The all-pairs table would be O(n^3) = 8 * 10^6 plus the
trouble of making nxt respect the tie-break, so the repeated single-source
search is both simpler and no slower here.
## Why the forward walk is the dictionary minimum
An arrow with w + distT[v] == distT[u] can still be completed at the optimal
remaining cost, so every such step keeps the route cheapest. The completions
available depend only on the current vertex, so a larger number now is never
repaid later, and taking the smallest legal next vertex at each step gives the
smallest sequence. Weights are at least 1, so distT strictly decreases and the
walk cannot loop.
## Cost
O(q * m log n) time and O(n + m) memory. A cheapest route is simple, so it
uses at most 199 arrows of up to 10^6, and a total stays under
2 * 10^8, inside the 2147483647 a signed 32 bit integer holds.
Constraints - `1 ≤ n ≤ 200` - `0 ≤ m ≤ 5000` - `1 ≤ q ≤ 200` - `1 ≤ w ≤ 1000000` - `1 ≤ s, t ≤ n`
Input
The first line contains three integers n, m and q.
Each of the next m lines contains three integers u, v and w: a directed arrow from u to v of weight w.
Each of the next q lines contains two integers s and t.
Output
Print q lines, one per question in the order asked. Each line holds the vertex numbers of the dictionary-smallest cheapest route from s to t separated by single spaces, or -1 if no route exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.