链接
题意
有一条长度为$n$的链,相邻的点之间的距离为1,再给出三条额外的边长度也为1。给出$m$组查询,查询$u$到$v$之间的距离,输出$S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$,$z_i$是第$i$次查询的结果。
思路
预处理出新加的边所连的点间的最段路,对于每次查询,枚举是否可以用新加的边的端点获得更短路径。
代码
|
|
A little brute force is always helpful.
有一条长度为$n$的链,相邻的点之间的距离为1,再给出三条额外的边长度也为1。给出$m$组查询,查询$u$到$v$之间的距离,输出$S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$,$z_i$是第$i$次查询的结果。
预处理出新加的边所连的点间的最段路,对于每次查询,枚举是否可以用新加的边的端点获得更短路径。
|
|