CF1566G Four Vertices

给定一个无向带权图，包含 $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$ 个整数，分别表示操作前和每次操作后，所选两对顶点之间的最短路径长度之和的最小值。

在操作前，可以选择顶点对 $(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$。 由 ChatGPT 4.1 翻译