分数: 550 点
问题陈述
在AtCoder的国家里,有 N 城市编号 1 to N,和 M 道路编号 1 to M.
路 i 连接城市 A_i 和 B_i 双向且长度为 C_i.
你被给予 Q 查询按顺序处理。查询有以下两种类型。
1 i:道路 i 关闭。2 x y: 打印距城市的最短距离 x 前往城市 y,仅使用未封闭的道路。如果城市 从城市无法到达 y 从城市无法到达 x,打印-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 关闭。
- 第五个查询中,city
当且仅当 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