[ABC375F]Road Blocked

题目描述

在 AtCoder 国家，有N座城市，编号为1至N，以及M条道路，编号为1至M。
道路i双向连接城市Ai​和Bi​，长度为Ci​。

给您Q个查询，请按顺序处理。这些查询有以下两种类型。

• 1 i:道路i关闭。
• 2 x y：打印从城市x到城市y的最短距离，只使用未关闭的道路。如果从城市x无法到达城市y，则打印-1。

保证每个测试用例最多包含第一种类型的300个查询。

输入描述

第一行N,M,Q代表有N座城市，M条道路，Q个询问

接下来M行，每行三个数代表城市Ai​和Bi之间长度为Ci

接下来Q行，代表Q个询问​

数据范围：

• 2≤N≤300
• 0≤M≤ $\frac{N(N+1)}{2}$
• 1≤$A_i$<$B_i$≤N
• 所有成对的($A_i$,$B_i$)都是不同的。
• 1≤$C_i$≤$10^9$
• 1≤Q≤2×$10^5$
• 在第一类查询中，1≤i≤M。
• 第一类查询中给出的道路当时尚未关闭。
• 第一种类型的查询次数最多为300。
• 第二种类型的查询次数为1≤x<y≤N。

输出描述

按照询问打印答案

提示

样例1 说明

• 在第一个查询中，打印从城市1到城市3的最短距离，即10。
• 在第二个查询中，道路2关闭。
• 在第三个查询中，打印从城市1到城市3的最短距离，即11。
• 在第四个查询中，道路1关闭。
• 在第五次查询中，从城市1无法到达城市3，因此打印-1。