The shortest loop
A bicycle courier warms up before a shift: they want to ride a loop and come back to where they started, without riding any street twice or passing through any intersection twice. The shorter the loop the better: the shift starts soon. Help find the length of the shortest such loop. It can start at any intersection.
The loop must pass through at least three different intersections: riding along a street and straight back is not a loop. Two tests are real streets: 150 intersections each in the centre of Almaty from OpenStreetMap, near Republic Square and near the Green Bazaar, with lengths in metres. In the real data the shortest loop turns out to be not a block at all but a triangle of short bits of street at an intersection.
Input
The first line holds n and m (1 ≤ n ≤ 150, 0 ≤ m ≤ n(n − 1)/2): the number of intersections and streets. Then come m lines a b w: a street between intersections a and b of length w, which can be ridden both ways (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ w ≤ 10⁶). There is at most one street between two intersections.
Output
The length of the shortest loop, or -1 if there are no loops.
Examples
Example 1
5 7 1 2 3 2 3 3 3 1 3 3 4 1 4 5 1 5 1 1 1 4 5
6
Example 2
4 3 1 2 7 2 3 2 2 4 9
-1
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 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
A loop is an edge (u, v) plus a path from v back to u. Why can’t you just take the shortest path from v to u from the Floyd–Warshall table?
2Hint 2
Let k be the vertex of the loop with the largest number. Which vertices lie on the rest of the loop? And what does the algorithm’s table know at that moment?
3The idea
The shortest path from v to u is often the edge (v, u) itself, and the “loop” comes out as a ride there and back. Paths must be forbidden from going through the vertices of the loop, and Floyd–Warshall gives such a ban for free. Take the vertex k of the loop with the largest number and its neighbours on the loop, i and j. The rest of the loop is a path from i to j all of whose vertices are less than k. Exactly such paths lie in the table before step k. So before step k check all pairs i < j < k: d[i][j] + w[j][k] + w[k][i].
4Walkthrough
Keep two tables: w, the streets themselves (infinity if there is no street), and d, the table of the algorithm, initially equal to w. For each k in order: first go over the pairs i < j < k that have streets to k and update the answer with the sum d[i][j] + w[j][k] + w[k][i]; then do the ordinary step of the algorithm through k.
Why this is always a real loop. Before step k the path from i to j goes only through vertices numbered less than k, so k is not on it; i ≠ j, and a shortest path with positive lengths does not repeat vertices. Adding k gives a loop of at least three vertices. Why the shortest will be found. Take the shortest loop and its vertex k with the largest number, with neighbours i and j. The rest of the loop is a path from i to j through vertices less than k, and d[i][j] before step k is no longer than it. So the check at step k finds a sum no greater than the length of this loop, and it cannot be smaller, since behind the sum stands a real loop.
The order “check, then update” is the main thing here. If you check after the step, the path from i to j may already go through k, and the sum describes a ride i → k → j → k → i along the same streets. On the first example such a solution answers 4 instead of 6.
For a single graph there is another way: for each street (u, v), remove it and find the shortest path from u to v with Dijkstra. This is O(m · m log n), worse than O(n³) for a dense graph.
4+Solution
5Complexity
O(n³) time: the steps of the algorithm are n³, the checks about n³/6. O(n²) memory for two tables.
6Common mistakes
- Checking after the step. The answer is smaller than the real one: the loop rides streets twice; the first example.
- The shortest path between the ends of a street. Without a ban this is the street itself, and the answer is twice the shortest street.
- A loop of two vertices. There and back along one street is not a loop, hence i ≠ j.
- No loops. The graph is a tree or a forest: the answer is
-1, the eighth test.