写在前面

看起来很简单的一个知识点 应用起来还是挺有学问的
所以趁着MB现在很饿不太想写题的时候来写一写自己对于动点spfa的理解

先说一说spfa

和另外几种常见的求解最短路的方法一样
spfa应用的前提是当前你已经知道了上一个位置的最优解了
比如说我现在在now节点,那么当我想更新to节点的最短路的时候,我一定知道了dis[now]的值,才能进行更新(就是熟悉的松弛操作)

动点spfa

有些时候,我们发现spfa这样的解决问题的方式并不适用于所有问题
举个例子
我现在不求最短路 求的是从s到t的一条路径 使得这条路径上的边权最大值-边权最小值最小
这个时候发现你无法用原来得到的某个点的答案进行更新
这个时候我们引入了动点spfa
上述问题的解决方式是什么呢
我们可以将边按从大到小的顺序排序 然后逐次向图中添加。
如果我们添加了一条边权为w的边 则说明这个图中目前的边边权都不小于w
也就是说对于任意一条从s到t的路径 边权最小值都不小于w
所以我们可以默认所有路径的最小边权都是w 我们就把问题转变成了求边权最大值最小的一条路径
然后我们就开心的用最短路就可以了
但是这样的话 我们发现
光头你跑了好多遍spfa 复杂度怎么保证
答案是 不能保证
所以我们考虑优化
我们发现每次加入节点之后 并不是所有的答案都会受到影响
这条边直接影响的最多只有两个点 即两个端点
对于这两个点 如果因为这条边的加入最优解发生了改变 就推入队列
然后跑最短路 得到新的解 更新答案
这就是动点spfa的解题思路
我们在碰到了无法通过只记录最优解就能解决问题的时候
这种问题一般是二维的
我们通过对一维进行排序 动态从小到大来加入确保这一维的最优性
然后维护第二维的最优解即可

一道例题

题目描述

negii在玩一个叫魔塔的游戏,这里我们的游戏略有不同。这里的地图是一个由n个点,m条边构成的无向连通图,negii现在在起点的位置,他需要到达每一个点之后才算游戏通关。但是每一条边上,都有一个守卫,你需要杀死他之后才能通过。每个守卫都有一定的攻击力和防御力,你需要保证的是的攻击力不小于对方的防御力,并且你的防御力不小于对方的攻击力,这样你才能打败当前的守卫。游戏最开始,negii的攻击力和防御力都为0,他需要通过金币购买来提升能力,negii每提升一点攻击力需要花费A个金币,每提升一点防御力需要B个金币,现在他想知道最少他需要花费多少金币才能通关。

输入

第一行,两个数n,m
接下来m行,每行4个数x,y,v,w,表示x,y之间存在一条有着防御力为v,攻击力为w的守卫的边

输出

一行一个数,表示答案,如果不存在,请输出-1

样例输入

3 3
2 1
1 2 10 5
1 2 4 10
1 3 5 1

样例输出

20

提示

对于40% :n<=100,m<=1500
对于另外10% :保证数据为一棵树
对于前70% :数据保证没有重边
对于100% :2<=n<=200,1<=m<=50000,A,B,v,w<=109

题解

这个题就是 我们明显看到了二维的东西
这个时候你会想 如果是一维该多么简单
直接最短路上去
二维的话我们就对第一维进行排序然后动态加入
每次推进去这条边的两个端点 然后用spfa进行对第二维最优解的维护
大概就是在维护最大值最小
然后进行更新
注意的是如果这个时候我们得到的值对应的点还没有被松弛的话我们就先不管他

代码