CF1566G Four Vertices

You are given an undirected weighted graph, consisting of $ n $ vertices and $ m $ edges. Some queries happen with this graph: - Delete an existing edge from the graph. - Add a non-existing edge to the graph. At the beginning and after each query, you should find four different vertices $ a $ , $ b $ , $ c $ , $ d $ such that there exists a path between $ a $ and $ b $ , there exists a path between $ c $ and $ d $ , and the sum of lengths of two shortest paths from $ a $ to $ b $ and from $ c $ to $ d $ is minimal. The answer to the query is the sum of the lengths of these two shortest paths. The length of the path is equal to the sum of weights of edges in this path.

N/A

N/A

Before the queries you can choose vertices $ (a, b) = (3, 2) $ and $ (c, d) = (1, 4) $ . The sum of lengths of two shortest paths is $ 3 + 1 = 4 $ . After the first query you can choose vertices $ (a, b) = (2, 5) $ and $ (c, d) = (1, 4) $ . The sum of lengths of two shortest paths is $ 2 + 1 = 3 $ . After the second query you can choose vertices $ (a, b) = (3, 4) $ and $ (c, d) = (2, 5) $ . The sum of lengths of two shortest paths is $ 1 + 2 = 3 $ . After the third query, you can choose vertices $ (a, b) = (2, 6) $ and $ (c, d) = (4, 5) $ . The sum of lengths of two shortest paths is $ 4 + 3 = 7 $ . After the last query you can choose vertices $ (a, b) = (1, 6) $ and $ (c, d) = (2, 5) $ . The sum of lengths of two shortest paths is $ 3 + 2 = 5 $ .