题目大意：
给定一个无向图，边权均为$a$，然后将原图中满足最短路等于$2a$的点对$(x,y)$之间再加一条边权为$b$的边。求$k$的单源最短路。
$PS.$各种乱搞，写不出来，只好膜题解。
题解：
不难想到的是，最短路只会是以下几种情况：
- 直接在原图上走最短路。
- 原图最短路，每两条边合并成一个$b$。(若长度为奇数，还要补一个$a$)
- 如果按2中的方案走，长度为奇数的路径是要补$a$的，但倘若$a$很大的话，那就不划算了。因而可以在原图上找到一种稍长的、但可以保证完美缩成若干$b$的路线，这样反而可以更短。
前两种情况比较好处理，直接跑最短路就可以了。由于边权都是$a$，因而可以直接用$BFS$，此时的复杂度为$O(m)$.
但第三种情况就不太好搞了，但我们可以尝试先写出暴力。
也可以用$BFS$。
对于当前出队列的点$p$，先向外扫描一圈把与之相邻的节点标记掉。（表示这些节点不能从$p$转移到。）此时$dis_p$为偶数个$a$，因而相邻节点与$s$的最短路(这里指可以被分为若干个$b$的最短路)，是不可以从$p$转移过来的。
之后对于每一个相邻节点，再搜它们的相邻节点，没有被标记的，且未被更新过的$dis$的节点入队列，并更新其$dis$(由$p$更新，$p$到它的最短路为$2a$，可以将其缩为一个$b$)。
最后要把与$p$相邻的节点的标记去掉。(因为可能以后会有别的点可以来更新它)
这样即可达到我们想要的效果，复杂度为$O(m^2)$。
但这样显然过不了，我们考虑优化。
取出队列开头的$p$后，遍历与它相邻的点的过程，我们称之为一次遍历。然后再遍历第二波节点，我们称之为二次遍历。
当一次遍历到一个节点$pp$以后，并由$pp$扩展到下一个节点$to$时，我们发现$(pp,to)$这一条边在以后的二次遍历中再也没有用了。因为$to$已经进入了队列，而$pp$没有，也就是说$pp$还有机会成为一次遍历产生的点，这时再由它第二次遍历时，原来已经进入队列的$to$就不需要再次进入了，所以该边可以删掉。(这里的删掉只是指在二次遍历中删掉，一次遍历还可能用到这些边)
因而我们一次遍历用原图的边，二次遍历的边可以不停地删掉。
对于删边的操作，我们可以用双向链表来存边已达到效果。
接下来我们分析一下复杂度：
首先，时间复杂度约等于遍历边的数量，所以我们只需要考虑那些遍历了却没有删掉的边的数量。
对于每一个节点$x$，由它开始进行一次遍历、再二次遍历中，没被删掉的边只有一种，就是在二次遍历中遍历到了一个与$x$距离为1的点，也就是说形成了一个三元环。所以对于这个节点$x$，假设和它距离为1的点有$k$个，那么这次最多有$k^2$条边被遍历了但没有删掉。又因为总共的边数为m，所以总的时间复杂度为:
$$\sum_{v \in{V}} min(degree(v^2),m) \le \sum_{v\in{V}} \sqrt{degree(v^2)*m} \le \sum_{v \in {V}}degree(v)*\sqrt{m}=O(m \sqrt{m})$$
Code:
|
|