AT_abc416_e [ABC416E] Development

AtCoder 国有 $1$ 到 $N$ 编号的 $N$ 个城市，$M$ 条道路，以及 $K$ 个机场。 第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，为双向道路，通行时间为 $C_i$。 机场位于城市 $D_1,\ldots,D_K$，有机场的城市之间可以以 $T$ 时间互相到达。 给定 $Q$ 个查询，请依次处理。查询有以下三种类型之一： - `1 x y t`：在城市 $x$ 和城市 $y$ 之间新建一条双向道路，通行时间为 $t$。 - `2 x`：在城市 $x$ 新建一个机场。 - `3`：设 $f(x,y)$ 为从城市 $x$ 到城市 $y$ 通过道路和机场可达时的最短时间，不可达时为 $0$。请计算 $\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)$。

输入以如下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ $C_1$ > $\vdots$ > $A_M$ $B_M$ $C_M$ > $K$ $T$ > $D_1$ $\dots$ $D_K$ > $Q$ > $\mathrm{Query}_1$ > $\vdots$ > $\mathrm{Query}_Q$ $\mathrm{Query}_i$ 表示第 $i$ 个查询，其格式和含义如题目描述所述。

对于每个第 $3$ 种类型的查询，依次输出答案，每行一个。

## 约束条件 - $1\leq N\leq 500$ - $0\leq M\leq 10^5$ - $1\leq A_i < B_i \leq N$ - $1\leq C_i \leq 10^9$ - $0\leq K\leq N$ - $1\leq T\leq 10^9$ - $1\leq D_1 < \dots < D_K \leq N$ - $1\leq Q\leq 1000$ - 对于第 $1$ 种类型的查询，$1\leq x < y \leq N$，$1\leq t\leq 10^9$ - 对于第 $2$ 种类型的查询，$1\leq x\leq N$ - 所有输入均为整数 ## 样例解释 1 AtCoder 国有 $4$ 个城市，最初城市 $1$ 和城市 $2$ 之间有一条通行时间为 $10$ 的道路，城市 $1$ 和城市 $3$ 之间有一条通行时间为 $100$ 的道路。 - 最初，$f(1,2)=f(2,1)=10,\ f(1,3)=f(3,1)=100,\ f(2,3)=f(3,2)=110$，其余均为 $0$，所以 $\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=440$。 - 新增一条城市 $2$ 和城市 $3$ 之间通行时间为 $60$ 的道路。 - $f(1,2)=f(2,1)=10,\ f(1,3)=f(3,1)=70,\ f(2,3)=f(3,2)=60$，其余均为 $0$，所以 $\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=280$。 - 新增一个机场在城市 $4$。 - $f(1,2)=f(2,1)=10,\ f(1,3)=f(3,1)=70,\ f(1,4)=f(4,1)=100,\ f(2,3)=f(3,2)=60,\ f(2,4)=f(4,2)=110,\ f(3,4)=f(4,3)=100$，其余均为 $0$，所以 $\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=900$。 同一对城市之间可以建多条道路，同一城市也可以建多个机场。 由 ChatGPT 4.1 翻译