← 返回题目
题库练习 Dynamic Shortest Path
← 上一题 下一题 →

A6174 | Dynamic Shortest Path

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个带权有向图，包含 $n$ 个顶点和 $m$ 条边。你需要回答 $q$ 个两种类型的询问：

- $1\ v$ —— 查询从顶点 $1$ 到顶点 $v$ 的最短路径长度。
- $2\ c\ l_{1}\ l_{2}\ ...\ l_{c}$ —— 对编号为 $l_{1}, l_{2}, ..., l_{c}$ 的边的权值各加 $1$。

输入格式

输入数据的第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m \leq 10^{5}$，$1 \leq q \leq 2000$），分别表示图中的顶点数、边数和询问数。

接下来的 $m$ 行描述边的信息：第 $i$ 行包含三个整数 $a_{i}$、$b_{i}$、$c_{i}$（$1 \leq a_{i}, b_{i} \leq n$，$0 \leq c_{i} \leq 10^{9}$），表示编号为 $i$ 的边从顶点 $a_{i}$ 指向 $b_{i}$，初始权值为 $c_{i}$。

接下来的 $q$ 行，每行为一条询问，格式如上（$1 \leq v \leq n$，$1 \leq l_{j} \leq m$）。保证每条第二类询问中的 $l_{j}$ 互不相同。且所有第二类操作涉及的边总数不超过 $10^6$。

输出格式

对于每一条第一类询问，输出一行，表示从顶点 $1$ 到顶点 $v$ 的最短路径长度。如果不存在这样的路径，输出 $-1$。

输入输出样例

输入 #1
3 2 9
1 2 0
2 3 0
2 1 2
1 3
1 2
2 1 1
1 3
1 2
2 2 1 2
1 3
1 2
输出 #1
1
0
2
1
4
2
输入 #2
5 4 9
2 3 1
2 4 1
3 4 1
1 2 0
1 5
1 4
2 1 2
2 1 2
1 4
2 2 1 3
1 4
2 1 4
1 4
输出 #2
-1
1
2
3
4
C++ 编辑器
输入
输出