#P6601. [2023山东第三轮省队集训]狞猎场
[2023山东第三轮省队集训]狞猎场
狩猎场
题目描述
娜娜奇住在深渊第四层,在与莉可等人相遇之前,这里就是它的狩猎场。
狩猎场是一张 个点、 条边的有向图,娜娜奇的家在顶点 。每条边带有边权,表示通过它所需的时间。每次前往某个顶点狩猎,娜娜奇都想知道从家出发的最短路径长度。
深渊不断变化,有些操作会让指定边的边权各增加 。按顺序处理所有修改与询问,回答每次询问时的最短路径长度。修改会一直保留,对后面的询问生效。
输入格式
从标准输入读取。
第一行三个整数 ,其中 是操作次数。
接下来 行,每行三个整数 ,表示一条从 指向 、初始边权为 的有向边。边按输入顺序编号为 ,顶点编号为 。
接下来 行,每行描述以下一种操作:
1 x:询问当前从顶点 到顶点 的最短路径长度;无法到达时输出 。2 k e1 e2 ... ek:将编号为 的 条不同边的边权各增加 。这些编号都在 至 中;同一条边可以在不同操作中多次增加。
输出格式
向标准输出输出每个类型 操作的答案,每个答案占一行。
样例输入
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
样例解释
修改前,到顶点 的最短距离为 ,到顶点 的最短距离为 。修改后前两条边权变为 ,到顶点 应直接走第三条边,距离为 。
原题另提到下发的其他样例,当前附件中未提供这些样例文件。
数据范围
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| ,,图是一棵以顶点 为根、边从父亲指向孩子的外向树 | ||
对于所有数据,。