F - Road Blocked Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

AtCoder国には 1 から N の番号がついた N 個の都市と、1 から M の番号がついた M 本の道路があります。
道路 i は都市 A_i と都市 B_i を双方向に結び長さは C_i です。

Q 個のクエリが与えられるので順に処理してください。クエリは以下の 2 種類のどちらかです。

  • 1 i：道路 i が通行止めとなる。
  • 2 x y：通行止めでない道路のみを通るときの都市 x から都市 y への最短距離を出力する。都市 x から都市 y に到達できないときは代わりに -1 を出力する。

なお、1 種類目のクエリはテストケースごとに 300 回以下であることが保証されます。

制約

  • 2 \leq N \leq 300
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1\leq A_i < B_i \leq N
  • (A_i,B_i) は相異なる
  • 1 \leq C_i \leq 10^9
  • 1 \leq Q \leq 2\times 10^5
  • 1 種類目のクエリにおいて、1\leq i \leq M
  • 1 種類目のクエリにおいて与えられる道路は、その時点で通行止めでない
  • 1 種類目のクエリは 300 回以下である
  • 2 種類目のクエリにおいて、1\leq x < y \leq N
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M Q
A_1 B_1 C_1
\vdots
A_M B_M C_M
\mathrm{query}_1
\vdots
\mathrm{query}_Q

各クエリは次の 2 種類の形式のどちらかである。

1 i

2 x y

出力

クエリを順に処理せよ。

入力例 1

3 3 5
1 2 5
1 3 10
2 3 6
2 1 3
1 2
2 1 3
1 1
2 1 3

出力例 1

10
11
-1
  • 1 番目のクエリでは、都市 1 から都市 3 への最短距離である 10 を出力します。
  • 2 番目のクエリにより、道路 2 が通行止めとなりました。
  • 3 番目のクエリでは、都市 1 から都市 3 への最短距離である 11 を出力します。
  • 4 番目のクエリにより、道路 1 が通行止めとなりました。
  • 5 番目のクエリでは、都市 1 から都市 3 には到達できないので、-1 を出力します。

入力例 2

4 6 6
2 3 1
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1
1 4
1 5
1 6
2 1 2
2 1 3
2 1 4

出力例 2

-1
-1
-1

Score : 550 points

Problem Statement

In the nation of AtCoder, there are N cities numbered 1 to N, and M roads numbered 1 to M.
Road i connects cities A_i and B_i bidirectionally and has a length of C_i.

You are given Q queries to process in order. The queries are of the following two types.

  • 1 i: Road i becomes closed.
  • 2 x y: Print the shortest distance from city x to city y, using only roads that are not closed. If city y cannot be reached from city x, print -1 instead.

It is guaranteed that each test case contains at most 300 queries of the first type.

Constraints

  • 2 \leq N \leq 300
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i < B_i \leq N
  • All pairs (A_i, B_i) are distinct.
  • 1 \leq C_i \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • In the queries of the first type, 1 \leq i \leq M.
  • The road given in a query of the first type is not already closed at that time.
  • The number of queries of the first type is at most 300.
  • In the queries of the second type, 1 \leq x < y \leq N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M Q
A_1 B_1 C_1
\vdots
A_M B_M C_M
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:

1 i

2 x y

Output

Process the queries in order.

Sample Input 1

3 3 5
1 2 5
1 3 10
2 3 6
2 1 3
1 2
2 1 3
1 1
2 1 3

Sample Output 1

10
11
-1
  • In the first query, print the shortest distance from city 1 to city 3, which is 10.
  • In the second query, road 2 becomes closed.
  • In the third query, print the shortest distance from city 1 to city 3, which is 11.
  • In the fourth query, road 1 becomes closed.
  • In the fifth query, city 3 cannot be reached from city 1, so print -1.

Sample Input 2

4 6 6
2 3 1
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1
1 4
1 5
1 6
2 1 2
2 1 3
2 1 4

Sample Output 2

-1
-1
-1