← 返回题目列表

AtCoder · abc375_f

I. 道路受阻

中文机器翻译题面 查看原题

分数: 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