← 返回题目列表

Codeforces · 843/D

D. 动态最短路径

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

给定一个带权有向图,由 n 个顶点和 m 个边组成。您应该回答 q 两种类型的查询:

- 1 v — 求从顶点 1 到顶点 v 的最短路径的长度。
- 2 c l1 l2 ... lc - 将索引为 l1, l2, ..., lc 的边的权重加 1。

输入

输入数据的第一行包含整数 n、m、q (1 ≤ n, m ≤ 105, 1 ≤ q ≤ 2000) — 图中的顶点和边的数量,以及相应的请求数量。

接下来 m 行输入数据包含边的描述:其中第 i 行包含索引为 i 的边的描述 — 三个整数 ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109) — 边的开始和结束,以及相应的初始权重。

接下来 q 行输入数据包含上述格式的边描述 (1 ≤ v ≤ n, 1 ≤ lj ≤ m)。保证在单个查询内所有 lj 都是不同的。并且保证第二类所有请求的边总数不超过106。

输出

对于第一种类型的每个查询,在单独的行中打印从 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

注意

第一个样例中图形的变化描述:第二个样例中图形的变化描述: