1746. The Next Cheapest Plan
An UNDIRECTED graph has n vertices and m edges, edge i joining u and v
at cost w. A PLAN is a set of edges that keeps every pair of vertices joined
that was joined to begin with, and uses no more edges than necessary; a cheapest
plan is what problem 1741 finds.
Print the smallest total of a plan STRICTLY DEARER than the cheapest, or -1 if
every plan costs the same as the cheapest.
4 vertices, 1-2 (1), 2-3 (2), 3-4 (3), 1-4 (9) -> 12 swap 3-4 for 1-4
3 vertices, 1-2 (5), 2-3 (5), 1-3 (5) -> -1 all plans cost 10
3 vertices, 1-2 (1), 2-3 (2) -> -1 only one plan exists
4 vertices, 1-2 (1), 2-3 (2), 1-3 (4), 3-4 (5) -> 10
The word STRICTLY is the whole statement. When the cheapest plan is not unique,
as in the second example, there are several plans at the cheapest total and
nothing above it, so the answer is -1 rather than that same total. Problem
1745 answers whether that case applies.
## The three things that have to be said
directed? no.
self-loops? allowed, and in no plan at all, so they are never swapped in.
parallel edges? allowed, and a duplicate at a dearer cost is a real
candidate swap.
disconnected? allowed. A plan is a spanning FOREST, and a swap may only
exchange edges inside one piece, never join two pieces.
## What most people try first
Removing each edge of the cheapest plan in turn, recomputing a cheapest plan of
what is left, and taking the smallest total above the cheapest. That is correct
and it runs Kruskal n times, so O(n m log m).
The quicker wrong idea is to add the cheapest unused edge and remove the
cheapest edge of the plan. The edge REMOVED has to lie on the path the new edge
closes, and the cheapest edge of the whole plan generally does not. On the
fourth example above the plan is 1-2 (1), 2-3 (2), 3-4 (5) costing 8, the only
unused edge is 1-3 (4), and the path it closes is 1-2, 2-3, so the dearest
edge on it is 2-3 at 2 and the answer is 8 + 4 - 2 = 10. Removing the
cheapest edge of the plan, 1-2 at 1, would give 11 and leave vertex 1 attached
only through 1-3, which is a plan, but a dearer one than necessary.
## Every second-best plan differs by exactly one swap
That is the fact everything rests on. Let T be a cheapest plan and S a
cheapest plan among those strictly dearer. Then S differs from T in exactly
one edge.
Why: S and T have the same size, so there is an edge f in S and not in
T. Adding f to T makes exactly one cycle, and that cycle contains an edge
e not in S, because otherwise the cycle would lie inside S. Swapping gives
T' = T + f - e, a plan, and S' = S - f + e, also a plan. The totals satisfy
cost(T') + cost(S') = cost(T) + cost(S). Since cost(T) is minimal,
cost(T') >= cost(T), hence cost(S') <= cost(S). If cost(S') > cost(T) then
S' is a strictly dearer plan at most as dear as S, so by minimality it is
exactly as dear, and repeating the argument reduces the difference to one edge.
If cost(S') == cost(T) then T' costs cost(S) and differs from T in one
edge, which is the claim.
## So: try every swap, but pick the right edge to remove
For each edge f not in the cheapest plan, with ends u and v and cost w:
walk the plan from u to v; that path is unique
let M be the largest cost on it and M2 the largest cost STRICTLY below M
the edge to remove is M if M < w, and M2 otherwise
candidate total = cheapest + w - (that cost)
Keep the smallest candidate that is strictly above the cheapest total. If there
is none, print -1.
Why the strictly-below part. If M == w, removing the edge of cost M and
adding f gives the SAME total, which is another cheapest plan, not a dearer
one. The next best swap along that path removes the dearest edge below w, and
that is M2. Tracking only the maximum, which is what the shorter version of
this algorithm does, reports the cheapest total as the answer on any input with
a tie and is wrong there.
An edge f whose ends lie in two DIFFERENT pieces cannot be swapped in at all,
because adding it would join two pieces and the result is not a forest of the
same shape. The walk reports that v is unreachable, and the edge is skipped.
## Cost
Time O(m log m + n m): Kruskal, then one walk of the plan per unused edge. At
n = 1000 and m = 5000 that is 5 * 10^6 steps. Space O(n + m). The walks
are ITERATIVE, since a plan can be a path through all n vertices. Totals reach
about 10^12, well past a 32-bit integer, so they are accumulated in 64 bits.
## Related
Problem 1741 finds the cheapest total and problem 1745 says whether it is
unique, which is exactly the condition under which this answers -1 for a
connected graph with a spare edge. Problem 1747 asks for the largest cost IN the
cheapest plan rather than the next total.
Constraints - `1 ≤ n ≤ 1000` - `0 ≤ m ≤ 5000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000` - `u` may equal `v`, so self-loops can occur, and costs may repeat - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected
Input
The first line contains two integers n and m, the number of vertices and the number of edges.
Each of the next m lines contains three integers u, v and w, an undirected edge joining u and v at cost w.
Output
Print one integer on its own line: the smallest total cost of a plan that is strictly dearer than the cheapest one. Print -1 if no plan costs more than the cheapest. The value can reach about 10^12, so print it as a 64-bit value.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.