计蒜客 - 闯关游戏 | SPFA

作者: jxtxzzw | 来源:发表于2020-04-07 20:37 被阅读0次

计蒜客 - 闯关游戏 | SPFA
计蒜客跳跃游戏二
计蒜客_新报数游戏
计蒜客-跳跃游戏(贪心)
计蒜客=跳跃游戏2(dp)
计蒜客（一）
Python资源
计蒜客题库五
计蒜客题库七
计蒜客题库六

今天分享一道有关 SPFA 单源最短路的算法题。

蒜头君在玩一个很好玩的游戏，这个游戏一共有至多 $100$ 个地图，其中地图 $1$ 是起点，房间 $n$ 是终点。有的地图是补给站，可以加 $k_i$ 点体力，而有的地图里存在怪物，需要消耗 $k_i$ 点体力，地图与地图之间存在一些单向通道链接。蒜头君从 $1$ 号地图出发，有 $100$ 点初始体力。每进入一个地图的时候，需要扣除或者增加相应的体力值。这个过程持续到走到终点，或者体力值归零就会 Game Over。不过，他可以经过同个地图任意次，且每次都需要接受该地图的体力值。

输入格式

第 $1$ 行一个整数 $n$ ( $n\leq 100$ )。

第 $2$ ~ $n+1$ 行，每行第一个整数表示该地图体力值变化。接下来是从该房间能到达的房间名单，第一个整数表示房间数，后面是能到达的房间编号。

输出格式

若玩家能到达终点，输出 Yes，否则输出 No。

No

首先我们来看一下什么是 SPFA。

众所周知，Dijkstra 算法不能处理有负权的图，而 Bellman-ford 算法通过对图进行 $|V| - 1$ 次松弛操作，得到所有可能的最短路径，而 SPFA（Shortest Path Faster Algorithm）通常被认为是 Bellman-ford 算法的队列优化，在代码形式上接近于宽度优先搜索 BFS，是一个在实践中非常高效的单源最短路算法。

需要指出的是，SPFA 的本质是 Bellman-ford 算法的队列优化，由于 SPFA 没有改变 Bellaman-ford 的时间复杂度，国外一般来说不认为 SPFA 是一个新的算法，而仅仅是 Bellman-ford 的队列优化。

在一定程度上，可以认为 SPFA 是由 BFS 的思想转化而来：从不含边权或者说边权为 1 个单位长度的图上的 BFS，推广到带权图上，就得到了 SPFA。SPFA 与 BFS 的不同在于，BFS 中一个点出了队列就不可能重新进入队列，但是 SPFA 中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。

SPFA 可以处理任意不含负环（负环是指总边权和为负数的环）的图的最短路，并能判断图中是否存在负环。

有了 BFS 的基础，我们很容易得到 SPFA 的算法描述：

d[i] 表示从源点 $s$ 到顶点 $i$ 的最短路，队列 q 保存即将进行拓展的顶点列表，inq[i] 标识顶点 $i$ 是不是在队列中；
初始队列中仅包含源点 $s$ ，且源点 $s$ 的 d[s] = 0。
取出队列头顶点 $u$ ，扫描从顶点 $u$ 出发的每条边，设每条边的另一端为 $v$ ，边 <u,v> 权值为 $w$ ，若 d[u] + w < d[v]，则将 d[v] 修改为 d[u] + w，若 $v$ 不在队列中，则将 $v$ 入队。重复步骤直到队列为空。
最终 d[] 数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队，则说明没有从源点到该顶点的路径。

void spfa(int s) {
    memset(inq, 0, sizeof(inq));
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    inq[s] = true;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int i = p[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (d[u] + e[i].w < d[v]) {
                d[v] = d[u] + e[i].w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

在进行 SPFA 时，用一个数组 cnt[i] 来标记每个顶点入队次数。如果一个顶点入队次数 cnt[i] 大于顶点总数 $n$ ，则表示该图中包含负环。

很显然，SPFA 的空间复杂度为 $\mathcal{O}(V)$ 。如果顶点的平均入队次数为 $k$ ，则 SPFA 的时间复杂度为 $\mathcal{O}(kE)$ ，对于较为随机的稀疏图，根据经验 $k$ 一般不超过 $4$ 。