/ 
Time Limit: 3.5 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
AtCoder 国には 1 から N の番号がついた N 個の街と、M 本の道路、K 個の空港があります。
i 番目の道路は街 A_i と街 B_i を双方向に結び、移動に C_i 時間かかります。
空港は街 D_1,\ldots,D_K にあり、空港がある街同士は T 時間で移動できます。
Q 個のクエリが与えられるので順に処理してください。クエリは次の 3 種類のいずれかです。
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) を求める。
制約
- 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 国には 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 です。
2つの街の間に複数の道路が作られることや、1つの街に複数の空港が作られることもあります。
Score : 450 points
Problem Statement
AtCoder Country has N cities numbered from 1 to N, M roads, and K airports.
The i-th road connects cities A_i and B_i bidirectionally and takes C_i hours to travel. There are airports in cities D_1,\ldots,D_K, and you can travel between cities with airports in T hours.
Process Q queries in order. Each query is one of the following three types:
1 x y t: A road connecting cities x and y bidirectionally in t hours is built.2 x: An airport is built in city x.3: Let f(x,y) be the smallest number of hours needed to reach city y from city x using roads and airports if reachable, and 0 if unreachable. Find \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y).
Constraints
- 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
- For type 1 queries: 1\leq x < y \leq N, 1 \leq t \leq 10^9.
- For type 2 queries: 1 \leq x \leq N.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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 represents the i-th query, whose format and meaning are as given in the problem statement.
Output
Output the answers to type 3 queries in order, separated by newlines.
Sample Input 1
4 1 1 2 10 2 100 1 3 5 3 1 2 3 60 3 2 4 3
Sample Output 1
440 280 900
AtCoder Country has four cities. Initially, there is a road connecting cities 1 and 2 in 10 hours, and airports connecting cities 1 and 3 in 100 hours.
- Initially, f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=100, f(2,3)=f(3,2)=110, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=440.
- A new road connecting cities 2 and 3 in 60 hours is built.
- f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70, f(2,3)=f(3,2)=60, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=280.
- A new airport is built in city 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, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=900.
Multiple roads may exist between some pair of cities. Also, a city may have multiple airports.