Road Blocked

题目描述

在 AtCoder 国，有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。
道路 $i$ 双向连接城市 $A_i$ 和 $B_i$，长度为 $C_i$。 给出 $Q$ 个按顺序处理的查询。查询有以下两种类型。

$1 i$：道路 $i$ 变为封闭。 $2 x y$：输出只使用未封闭道路时从城市 $x$ 到城市 $y$ 的最短距离。如果城市 $y$ 无法从城市 $x$ 到达，输出 $-1$。

保证每个测试用例中第一类查询的数量最多为 $300$。

输入格式

输入从标准输入以以下格式给出： $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$

输出格式

按顺序处理查询。

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

10
11
-1

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

-1
-1
-1

提示

$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。 所有输入值均为整数。在第一个查询中，输出从城市 $1$ 到城市 $3$ 的最短距离，为 $10$。 在第二个查询中，道路 $2$ 变为封闭。 在第三个查询中，输出从城市 $1$ 到城市 $3$ 的最短距离，为 $11$。 在第四个查询中，道路 $1$ 变为封闭。 在第五个查询中，城市 $3$ 无法从城市 $1$ 到达，因此输出 $-1$。

标签: AtCoder|abc375F

来源

AtCoder|abc375F