← 返回题目列表

Codeforces · 1566/G

G. 四个顶点

中文机器翻译题面 查看原题

给你一个无向加权图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。

此图发生一些查询:

- 从图表中删除现有边。
- 向图中添加一条不存在的边。

在每个查询的开始和之后,您应该找到四个不同的顶点 $$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$,使得 $$$a$$$ 和 $$$b$$$ 之间存在路径,$$$c$$$ 和 $$$d$$$ 之间存在路径,以及从$$$a$$$ 到 $$$b$$$ 以及从 $$$c$$$ 到 $$$d$$$ 是最小的。查询的答案是这两条最短路径的长度之和。路径的长度等于该路径中边的权重之和。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(4 \le n, m \le 10^5)$$$ - 分别是图中的顶点数和边数。

接下来的 $$$m$$$ 行包含三个整数 $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \le v, u \le n, v \neq u$$$, $$$1 \le w \le 10^9$$$) - 这个三元组意味着顶点 $$$v$$$ 和$$$u$$$ 重量为 $$$w$$$。

下一行包含一个整数 $$$q$$$ $$$(0 \le q \le 10^5)$$$ — 查询数。

接下来的 $$$q$$$ 行包含两种类型的查询:

- $$$0$$$ $$$v$$$ $$$u$$$ - 此查询意味着删除 $$$v$$$ 和 $$$u$$$ $$$(1 \le v, u \le n, v \neq u)$$$ 之间的边。保证图中存在这样的边。
- $$$1$$$ $$$v$$$ $$$u$$$ $$$w$$$ - 此查询意味着在顶点 $$$v$$$ 和 $$$u$$$ 之间添加一条边,权重为 $$$w$$$ ($$$1 \le v, u \le n, v \neq u$$$, $$$1 \le w \le 10^9$$$)。保证图中不存在这样的边。

保证初始图不包含多条边。

在每次查询开始时和之后,不需要连接图。

保证每一时刻的边数至少为$$$4$$$。可以证明,每一时刻都存在四个顶点$$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$,使得顶点$$$a$$$和$$$b$$$之间存在路径,顶点$$$c$$$和$$$d$$$之间存在路径。

输出

打印 $$$q + 1$$$ 整数 - 查询之前和每个查询之后所选顶点对之间最短路径长度的最小总和。

示例

输入 #1

6 6
1 3 6
4 3 1
1 4 1
2 6 4
2 4 2
5 4 3
4
1 2 5 2
0 1 4
0 3 4
1 6 1 3

输出 #1

4
3
3
7
5

注意

在查询之前,您可以选择顶点 $$$(a, b) = (3, 2)$$$ 和 $$$(c, d) = (1, 4)$$$。两条最短路径的长度之和为$$$3 + 1 = 4$$$。

第一次查询后,您可以选择顶点 $$$(a, b) = (2, 5)$$$ 和 $$$(c, d) = (1, 4)$$$。两条最短路径的长度之和为$$$2 + 1 = 3$$$。

第二次查询后,您可以选择顶点 $$$(a, b) = (3, 4)$$$ 和 $$$(c, d) = (2, 5)$$$。两条最短路径的长度之和为$$$1 + 2 = 3$$$。

第三次查询后,您可以选择顶点 $$$(a, b) = (2, 6)$$$ 和 $$$(c, d) = (4, 5)$$$。两条最短路径的长度之和为$$$4 + 3 = 7$$$。

最后一次查询后,您可以选择顶点 $$$(a, b) = (1, 6)$$$ 和 $$$(c, d) = (2, 5)$$$。两条最短路径的长度之和为$$$3 + 2 = 5$$$。