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 翻译