103755: [Atcoder]ABC375 F - Road Blocked

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

问题陈述

在AtCoder国，有N个城市，编号为1到N，和M条道路，编号为1到M。
道路i双向连接城市A_i和B_i，长度为C_i。

你需要按顺序处理Q个查询。查询有以下两种类型。

• 1 i：道路i被关闭。
• 2 x y：打印从城市x到城市y的最短距离，只能使用未关闭的道路。如果从城市x无法到达城市y，则打印-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 \leq i \leq M$。
• 在第一种类型的查询中给出的道路在那时还没有被关闭。
• 第一种类型的查询数量最多为300。
• 在第二种类型的查询中，$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$

每个查询的格式如下：

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到城市3的最短距离，为10。
• 在第二个查询中，道路2被关闭。
• 在第三个查询中，打印从城市1到城市3的最短距离，为11。
• 在第四个查询中，道路1被关闭。
• 在第五个查询中，城市3无法从城市1到达，所以打印-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