A spare route
A fire station needs two routes from the depot to a site: a primary and a backup. So that a blocked crossing does not affect both at once, the routes must have no common crossings other than the start and the end. Of all such pairs, the one with the smallest sum of lengths is needed. If there is no pair, say so.
Tests 3–4 are real streets of central Almaty from OpenStreetMap: 7909 crossings; in the third test the routes lead from fire stations to well-known places in the city. All streets are considered two-way.
Input
The first line holds n and m, the number of crossings and streets (2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 2 · 10⁴). Then m lines a b ℓ: a street of length ℓ metres between crossings a and b (a ≠ b, 1 ≤ ℓ ≤ 10⁴, at most one street between two crossings). Then the number of queries q (1 ≤ q ≤ 20) and q lines s t (s ≠ t).
Output
For each query, the smallest sum of lengths of two routes from s to t without common crossings other than s and t, or -1 if there is no such pair. A street directly from s to t is a route too, but only one.
Examples
Example 1
4 4 1 2 3 2 4 4 1 3 5 3 4 6 3 1 4 1 2 2 3
18 18 18
Example 2
7 8 1 2 1 2 3 1 3 4 1 1 5 2 5 3 2 2 6 2 6 4 2 4 7 1 3 1 4 1 5 1 7
10 6 -1
Limits
- Time · Python
- 12500 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The shortest route, and then the shortest around its crossings? Look at the second example: the shortest route 1 → 2 → 3 → 4 takes both crossings through which one could go around, and there is no second route around it. But a pair exists: 1 → 5 → 3 → 4 and 1 → 2 → 6 → 4.
2Hint 2
Two routes without common crossings are a flow of value 2 in which at most one unit passes through each crossing. What should be done with a crossing to limit the flow through it? And what should be minimised?
3The idea
Turn each crossing v into two vertices, an entrance and an exit, with an arc of capacity 1 between them; for s and t the capacity is 2. Each street is two arcs of capacity 1 and cost ℓ, one in each direction. The answer is a minimum-cost flow of value 2 from s to t: two units, each along the cheapest path in the residual network. The second path may go along part of the first backwards, along reverse arcs of negative cost, and so take a piece away from the first route. In the second example it works out exactly so: 1 → 5 → 3, back 3 → 2, then 2 → 6 → 4.
4Walkthrough
Build the network once, and for each query copy the array of capacities and set 2 on the arcs of s and t. Two Dijkstra searches on reduced costs c + π(u) − π(v): before the first all potentials are zero, and after each the distances are added to them. If the second search did not reach the sink, there is no pair, and the answer is −1. The cost of the flow is the sum of the costs of the arcs traversed, with negative cancellations already subtracted.
Why two independent arcs per street rather than one undirected: the second path may go along a street of the first one in the opposite direction, and that must be a reverse arc of negative cost, not another unit of flow along the same street.
4+Solution
5Complexity
Two searches on a network of 2n vertices and 2n + 4m arcs: O((n + m) log n) per query. Suurballe’s algorithm is built the same way: exactly two shortest path searches.
6Common mistakes
- The shortest, then the shortest around it. This is
wrong.py. In the second example it finds no second route. On the streets of Almaty, among queries where a pair exists, it is wrong in 10 of 17 in the third test and in 16 of 19 in the fourth: the pair comes out longer, and once there is no second route at all. In the seventh test the shortest route zigzags between the two rails of a long ladder and blocks both, although the rails themselves are the best pair. - Without splitting crossings. Capacity 1 on streets only gives routes without common streets but with common crossings.
- Dijkstra without potentials on the second search: the reverse arcs of the first path are negative, and an ordinary Dijkstra may return a path that is not the cheapest.
Algorithms behind it
O(F · E log V)
2 problems
GRA
Algorithm
Dijkstra's algorithm
Shortest paths from one vertex in a weighted graph without negative edges.
O((V + E) log V)
3 problems