CF25C Roads in Berland

在 Berland 有 $n$ 个城市，编号从 $1$ 到 $n$。其中一些城市由双向道路连接。每条道路的长度为 $1$ 到 $1000$ 的整数。已知从任意一个城市出发都可以通过已有的道路到达其它任意城市。并且，对于每对城市，已知它们之间的最短距离。 Berland 政府计划修建 $k$ 条新道路。对于每条计划中的新道路，均已知其长度，以及它将连接的两个城市。为了控制新路建设的正确性，在每一条新路建成以后，Berland 政府希望检查所有城市对之间的最短距离之和。 现在，请你帮忙：对于给定的原有道路最短距离矩阵，以及所有新道路的建设计划，求在每建成一条新道路以后，所有城市对的最短距离之和是如何变化的。

第一行输入整数 $n$（$2 \leq n \leq 300$），表示 Berland 的城市数。 接下来 $n$ 行，每行有 $n$ 个整数，表示当前的最短距离矩阵。第 $i$ 行第 $j$ 个数 $d_{i,j}$ 表示城市 $i$ 到城市 $j$ 的最短距离。保证 $d_{i,i}=0$，且 $d_{i,j}=d_{j,i}$，并且给定的矩阵确实为某种双向道路网络的最短距离矩阵（道路长度为 $1$ 到 $1000$ 的整数），且任意城市之间总是连通的。 接下来一行输入整数 $k$（$1\leq k\leq 300$），表示计划修建的新道路条数。 接下来的 $k$ 行，每行三个用空格分隔的整数 $a_i, b_i, c_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq c_i \leq 1000$），表示第 $i$ 条计划新建的道路连接了城市 $a_i$ 和 $b_i$，长度为 $c_i$。一对城市之间可能有多条道路，但不会有连接自身的道路。

输出 $k$ 个用空格分隔的整数 $q_i$（$1 \leq i \leq k$）。其中 $q_i$ 表示修建完第 $1$ 到第 $i$ 条新道路后，所有城市对之间的最短距离之和。每对城市只统计一次，即只考虑无序对。

由 ChatGPT 5 翻译