SP7025 CT25C - Roads in Berland

Berland 有 $n$ 个城市，这些城市由编号 1 到 $n$ 标识，有若干双向道路将部分城市相连。每条道路都有一个距离值，为 1 到 1000 的整数。确保从任何一个城市都可以通过现有的道路到达其他每个城市。此外，对于城市间的每一对城市，已知它们之间的最短距离。现在，Berland 政府计划修建 $k$ 条新道路。对于每条计划中的新道路，除了道路长度外，还有其连接的城市信息。为了确保新道路建成后的合理性，政府希望在每条新道路开通后，核算所有城市之间最短路径总和的变化。请帮助他们解决这个问题，基于给定的旧道路的距离矩阵和新道路的计划，找出在每条新道路建成后，所有城市对之间最短距离总和的变化。

第一行是一个整数 $n$ （$2 \le n \le 300$），表示 Berland 的城市数量。接下来 $n$ 行中，每行包含 $n$ 个整数，形成一个距离矩阵。矩阵中第 $i$ 行第 $j$ 列的数 $d_{i, j}$ 表示城市 $i$ 和城市 $j$ 之间的距离。保证 $d_{i, i} = 0$，并且 $d_{i, j} = d_{j, i}$，即这已是一个已知的双向道路网络的距离矩阵，确保任意城市间都可通过该网络互相连通。 接下一个整数 $k$ （$1 \le k \le 300$），表示计划修建的新道路数量。接下来的 $k$ 行分别描述了每条新修建道路的信息。每行包含三个用空格隔开的整数 $a_i$, $b_i$, $c_i$ （$1 \le a_i, b_i \le n$，$a_i \neq b_i$，$1 \le c_i \le 1000$），对应这条新道路连接的城市对（即 $a_i$ 和 $b_i$）及其长度 $c_i$。可以出现多条连接相同城市对的道路，但不会有道路与自身相连。

输出共 $k$ 行，每行一个整数 $q_i$ （$1 \le i \le k$）。$q_i$ 代表在前 $i$ 条新建道路都开通后，所有城市对的最短距离之和。每对城市在求和中只计算一次，即只考虑城市对的无序组合。 **本翻译由 AI 自动生成**