AT_abc375_f [ABC375F] 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$ 的最短距离。如果无法到达，则输出 $-1$。

另外，保证每个测试用例中第 $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$

输出格式

请依次输出每个查询的结果。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

说明/提示

数据范围

• $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$
• 输入均为整数

样例说明 1

• 第 $1$ 个查询，输出从城市 $1$ 到城市 $3$ 的最短距离 $10$。
• 第 $2$ 个查询，将第 $2$ 条道路封闭。
• 第 $3$ 个查询，输出从城市 $1$ 到城市 $3$ 的最短距离 $11$。
• 第 $4$ 个查询，将第 $1$ 条道路封闭。
• 第 $5$ 个查询，无法从城市 $1$ 到城市 $3$，输出 $-1$。

由 ChatGPT 4.1 翻译