P2604 [ZJOI2010]网络扩容

题目描述

现在有一张无向图，你需要对这张图进行$m$次操作。每次操作有以下两种：

- 将一条边$(u,v)$的权值增加$k$
- 查询点$x$到点$y$的最短路长度

输入格式

第1行：三个正整数$n,m,k$表示点数，操作数和每次操作增加的权值。

第2~$n+1$行：每行$n$个整数，表示图的邻接矩阵，其中第$i$行第$j$列的整数表示$(i,j)$边的长度，如果为0，则表示这条边不存在。

第$n+2$~$n+m+1$行：每行代表一个操作，格式为：

- 格式1：1 $x$ $y$，表示将$x$到$y$的边的权值增加$k$。
- 格式2：2 $x$ $y$，表示查询$x$到$y$的最短路长度。

输出格式

对于每个操作2，输出一个查询结果，每个结果占一行。

数据范围

$1\leq n\leq400,1\leq m\leq20000,1\leq k\leq100$

输入样例1

4 5 1
0 2 0 2
2 0 1 0
0 1 0 1
2 0 1 0
2 1 2
1 1 3
2 1 2
2 1 4
1 2 3

输出样例1

3
5
6

输入样例2

4 5 2
0 2 0 2
2 0 1 0
0 1 0 1
2 0 1 0
2 1 2
1 1 3
2 1 2
2 1 4
1 2 3

输出样例2

4
6
8

算法

(floyd,最短路) $O(n^3m)$

C++ 代码

相关问题

zjoi2019 浙江省选

zjoi2019是指第八届浙江省信息学奥林匹克竞赛（Zhejiang Olympiad in Informatics, zjoi），是浙江省级的信息学竞赛活动。这项竞赛旨在发掘和培养浙江省优秀的信息学人才，提高学生在计算机科学和算法设计等方面的能力。zjoi2019分为两个阶段，分别是省赛和决赛。

省赛是选拔赛阶段，所有报名参赛的学生都可以参加。在省赛中，学生将进行一系列的算法编程测试，测试他们在解决实际问题过程中的编程能力、算法设计思维和团队合作能力。省赛中表现优秀的选手将有机会晋级到决赛。

决赛是省选的最终阶段，在决赛中，选手将经历更加复杂和挑战性的编程测试。他们将面对更高难度的算法问题和实际应用问题，需要发挥出自己的创造力和思维能力，迅速解决问题。决赛中表现出色的选手将有机会代表浙江省参加全国性的信息学奥林匹克竞赛。

通过参加zjoi2019浙江省选，学生们将接触到高水平的算法竞赛，提升自己的编程和算法设计能力。同时，他们还能与其他对信息学感兴趣的同学们进行交流和学习，拓宽自己的视野，培养团队合作和竞赛意识。此外，脱颖而出的选手还有机会获得奖项和奖学金等荣誉，为自己的学术和职业道路打下坚实的基础。

总之，zjoi2019浙江省选是对浙江省信息学人才的全面选拔和培养，为学生们提供了一个展示自己技能和才华的舞台。这对于提高学生们的算法设计和编程能力、培养他们的团队合作精神和创新能力具有重要意义。