#P18776. [Kaist2021]Dynamic Short Path
[Kaist2021]Dynamic Short Path
Dynamic Short Path
题目描述
给定一个有 个顶点、 条边的有向图。对于任意不同的顶点 ,均有一条从 到 的有向边,权值 为 、 或 。
按顺序处理 次操作:
1 a b:设从 到 的最短路长度为 ,输出 。允许 ,此时最短路长度为 。2 a b c:将边 的权值改为 ,其中 。
第二类操作至多出现 次。
输入格式
第一行两个整数 。
接下来 行,每行 个整数,第 行第 个整数为 。图中没有自环,但输入中的 固定写为 。
接下来 行,每行按上述格式描述一次操作。
输出格式
对于每次第一类操作,输出一行一个整数,表示该次询问的答案。
数据范围
- ,。
- ,。
- 修改操作中 ,修改总数不超过 。
- 至少包含一次询问。
样例 1
输入
5 10
0 1 2 2 2
2 0 2 2 2
2 2 0 1 2
2 2 2 0 2
2 2 2 2 0
1 1 2
1 2 1
1 1 3
1 1 4
1 4 5
1 5 5
2 4 5 0
1 4 5
1 2 5
1 1 5
输出
1
2
2
2
2
0
0
2
2