分数: 450 点
问题陈述
AtCoder 国家有 N 城市编号自 1 to 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) 是到达城市所需的最少小时数 y 来自城市 x 使用道路和机场(如果可以到达),并且 0 如果无法访问。查找 \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y).
约束
- 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
4 1 1 2 10 2 100 1 3 5 3 1 2 3 60 3 2 4 3
示例输出 1
440 280 900
AtCoder国家有四个城市。最初,有一条道路连接城市 1 和 2 in 10 时间,以及连接城市的机场 1 和 3 in 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 in 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.
某些城市之间可能存在多条道路。 此外,一个城市可能有多个机场。