#P6601. [2023山东第三轮省队集训]狞猎场

    ID: 6451 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-图论Dijkstra势能重赋权CF2400

[2023山东第三轮省队集训]狞猎场

狩猎场

题目描述

娜娜奇住在深渊第四层,在与莉可等人相遇之前,这里就是它的狩猎场。

狩猎场是一张 nn 个点、mm 条边的有向图,娜娜奇的家在顶点 11。每条边带有边权,表示通过它所需的时间。每次前往某个顶点狩猎,娜娜奇都想知道从家出发的最短路径长度。

深渊不断变化,有些操作会让指定边的边权各增加 11。按顺序处理所有修改与询问,回答每次询问时的最短路径长度。修改会一直保留,对后面的询问生效。

输入格式

从标准输入读取。

第一行三个整数 n,m,qn,m,q,其中 qq 是操作次数。

接下来 mm 行,每行三个整数 u,v,cu,v,c,表示一条从 uu 指向 vv、初始边权为 cc 的有向边。边按输入顺序编号为 1,…,m1,\ldots,m,顶点编号为 1,…,n1,\ldots,n。

接下来 qq 行,每行描述以下一种操作:

  • 1 x:询问当前从顶点 11 到顶点 xx 的最短路径长度;无法到达时输出 −1-1。
  • 2 k e1 e2 ... ek:将编号为 e1,…,eke_1,\ldots,e_k 的 kk 条不同边的边权各增加 11。这些编号都在 11 至 mm 中;同一条边可以在不同操作中多次增加。

输出格式

向标准输出输出每个类型 11 操作的答案,每个答案占一行。

样例输入

3 3 5
1 2 3
2 3 4
1 3 8
1 2
1 3
2 2 1 2
1 2
1 3

样例输出

3
7
4
8

样例解释

修改前,到顶点 22 的最短距离为 33,到顶点 33 的最短距离为 3+4=73+4=7。修改后前两条边权变为 4,54,5,到顶点 33 应直接走第三条边,距离为 88。

原题另提到下发的其他样例,当前附件中未提供这些样例文件。

数据范围

子任务 分值 附加限制
11 1515 n,m≤1000n,m\leq1000
22 3535 m=n−1m=n-1,n≤100000n\leq100000,图是一棵以顶点 11 为根、边从父亲指向孩子的外向树
33 5050 n,m≤100000n,m\leq100000

对于所有数据,q≤2000q\leq2000。