← 返回题目列表

AtCoder · abc416_e

H. 发展

中文机器翻译题面 查看原题

分数: 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.

某些城市之间可能存在多条道路。 此外,一个城市可能有多个机场。