Visits: 296

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

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

输入格式

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

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

5
0 1 2
-60 1 3
-60 1 4
20 1 5
0 0

输出格式

若玩家能到达终点，输出 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 的算法描述：

1. d[i] 表示从源点 $s$ 到顶点 $i$ 的最短路，队列 q 保存即将进行拓展的顶点列表，inq[i] 标识顶点 $i$ 是不是在队列中；
2. 初始队列中仅包含源点 $s$，且源点 $s$ 的 d[s] = 0。
3. 取出队列头顶点 $u$，扫描从顶点 $u$ 出发的每条边，设每条边的另一端为 $v$，边 <u,v> 权值为 $w$，若 d[u] + w < d[v]，则 将 d[v] 修改为 d[u] + w，若 $v$ 不在队列中，则将 $v$ 入队。重复步骤直到队列为空。
4. 最终 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$。

对于稀疏图而言，SPFA 相比堆优化的 Dijkstra 有很大的效率提升，但是对于稠密图而言，SPFA 最坏为 $\mathcal{O}(VE)$，远差于堆优化 Dijkstra 的 $\mathcal{O}((V+E)logV)$。

在看完了 SPFA 之后，这道题就比较容易了。

在套用 SPFA 模板的时候，注意要初始化 d[] 数组为负无穷大，并设置起点的体力值为 d[s] = 100。

然后在 SPFA 的判断条件中 if (d[u] + e[i].w < d[v]) 改成 if (d[u] + e[i].w > d[v]) 因为我们需要保留体力最大的。

另外在每一个点入队以后，令 cnt[i]++，若等于 $n$，说明有环，那么蒜头君就可以无限制地往这个点走，最终体力为无穷大，再也不需要考虑其他点的体力值了，因此一定可以走到终点。所以直接 return，并直接输出 Yes。

最后的输出结果就是 d[n] > 0。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3F3F3F3F;

const int MAX_N = 100;
const int MAX_M = 10000;
bool inq[MAX_N];
int d[MAX_N];  // 如果到顶点 i 的距离是 0x3F3F3F3F，则说明不存在源点到 i 的最短路
int cnt[MAX_N];
int n;

struct edge {
    int v, next, w;
} e[MAX_M];
int p[MAX_N], eid;

void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int w) {
    e[eid].v = v;
    e[eid].next = p[u];
    e[eid].w = w;
    p[u] = eid++;
}

// SPFA 算法
void spfa(int s) {
    memset(inq, 0, sizeof(inq));
    memset(d, -0x3F, sizeof(d)); // 套用模板，初始化为负无穷
    memset(cnt, 0, sizeof(cnt));
//    d[s] = 0;
    d[s] = 100; // 套用模板，初始体力是 100
    inq[s] = true;
    queue<int> q;
    q.push(s);
    cnt[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]) {
            if (d[u] + e[i].w > d[v]) {  // 套用模板，要保留走过去的时候生命值最大的
                d[v] = d[u] + e[i].w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                    cnt[v]++;
                    if (cnt[v] == n) {
                        // 如果一个点入队 n 次，说明这个点能无限增加体力
                        // 置终点的剩余体力为无穷大
                        d[n] = INF;
                        return;
                    }
                }
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    init();
    // 本题 id 从 1 开始
    for (int i = 1; i <= n; i++) {
        int hp, rooms, to;
        scanf("%d%d", &hp, &rooms);
        for (int j = 0; j < rooms; j++) {
            scanf("%d", &to);
            insert(i, to, hp);
        }
    }

    // 从起点开始做单源最短路
    spfa(1);

    // 最终输出的结果是：达到终点的时候体力还大于 0 吗
    printf("%s", d[n] > 0 ? "Yes" : "No");
}