SPFA-BFS 的一种扩展

一句话总结本篇题解内容:BFS 中每个点只入列一次，但有时，我们可能需要 BFS 中允许一个点入列多次才能解决问题，这种方法就是 SPFA。

简介

SPFA 这种算法，如果你百度的话，你会发现大多是说他用于求最短路的，事实上，更宽泛的来理解，所有“可能要后悔”的 BFS，都可以用类似 SPFA 的思路来解决。

先说说经典的最短路问题，希望大家能借此理解为何说 SPFA 是可以“后悔”的。

经典问题

考虑这样一张图，1 号点是起点，边上的数字代表这条边的长度，你想求出 1 到 10 号点的最短路。

下面，说说为何朴素的 BFS 不行。

按照 BFS 的流程，初始 1 号点入列，然后 1 号点周围的 2 号和 3 号入列。此时，2 距 1 最短路更新为 4,3 距 1 最短路更新为 1。

于是，问题来了，我们看到，实际上 1 到 2 的最短路是1->3->4->2，其长度为 3。

但按照朴素的 BFS 来做，由于已经有 vis[2]=1 了，所以由 4 号点访问周围点时，2 号点就不会再入列了，这样，我们就会求出错误的最短路。

那怎么办呢？一个很显然的办法，就是——那我就再把 2 入列呗！

SPFA 算法

所以，SPFA 其实就是很简单的一件事儿：检测到某点距离变化，就把某点入列。

并且如前所述，这样的 SPFA 其实就不需要 vis 数组了，因为只要距离更新，点就要入列。

但下面代码中还是有 vis 数组，其实他的含义是：某个点当前正在队列里，vis值为 1，当前点不在队列里，vis值为 0。

需要注意，虽然名字都叫 vis，但这里的vis 数组和朴素 BFS 中的 vis 数组很不一样。

这里 vis 数组只是避免同一个点已经在队列里的情况下被加入队列多次而用的（再次强调，SPFA 是允许一个点多次入列的，只不过正在队列里的，确实没必要再入列了）。

那么具体看这道题，dis[i][j]表示到达第 i 行第 j 列的点所需要的最小花费，直接的状态转移看上去并不好想。

怎么办？

不好想就不想了呗！

只要某个点 dis 变得更小了，我们按照 SPFA 的思想，就二话不说给他入列，让他再更新周围点的dis，这样总是对的了吧。

所以说白了，SPFA，听上去高大上，其实是贼暴力的一种方法，只要检测到某点 dis 值改变，就在重新由这点开始 BFS，仅此而已。

代码

下面是代码：

#define INF 10005
int dis[105][105];
bool inQue[105][105];
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n=grid.size();int m=grid[0].size();
        memset(dis,INF,sizeof(dis));
        memset(inQue,false,sizeof(inQue));

        queue<pair<int,int>> q;
        q.push(make_pair(0,0));
        inQue[0][0]=true;
        dis[0][0]=0;

        while(!q.empty()){
            auto now=q.front();q.pop();
            int x=now.first;int y=now.second;
            inQue[x][y]=false;
            for(int k=1;k<5;k++){
                if(x+dx[k]<0||x+dx[k]>=n||y+dy[k]<0||y+dy[k]>=m)continue;

                int val= k==grid[x][y]?dis[x][y]:dis[x][y]+1;
                if(dis[x+dx[k]][y+dy[k]]>val){
                    dis[x+dx[k]][y+dy[k]]=val;
                    if(!inQue[x+dx[k]][y+dy[k]]){
                        q.push(make_pair(x+dx[k],y+dy[k]));
                        inQue[x+dx[k]][y+dy[k]]=true;
                    }
                }
            }
        }

        return dis[n-1][m-1];
    }
};

leetcode 5699

#define PII pair<int, int>
#define MP(x, y) make_pair(x, y)

const int MOD = 1e9 + 7;
const int MAXN = 2e4 + 50;
queue<int> que;
int dist[MAXN], idx[MAXN], ans[MAXN];
bool inQue[MAXN];
vector<PII> edge[MAXN];

bool cmp(int a, int b){ return dist[a] < dist[b]; }

class Solution {
public:
    void SPFA(int src, int n){
        for (int i = 0; i <= n; i++) inQue[i] = false, dist[i] = -1;
        while(!que.empty()) que.pop();

        que.push(src); dist[src] = 0; inQue[src] = true;
        while(!que.empty()){
            int x = que.front(); que.pop();
            for (PII& e: edge[x]){
                int y = e.first, w = e.second;
                if (dist[y] == -1 || dist[y] > dist[x] + w){
                    dist[y] = dist[x] + w;
                    if (!inQue[y]) inQue[y] = true, que.push(y);
                }
            }
            inQue[x] = false;
        }
    }
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        for (int i = 0; i <= n; i++) edge[i].clear();
        for (vector<int>& e: edges){
            int x = e[0], y = e[1], w = e[2];
            edge[x].push_back(MP(y, w));
            edge[y].push_back(MP(x, w));
        }

        SPFA(n, n);

        for (int i = 1; i <= n; i++) idx[i] = i, ans[i] = 0;
        sort(idx + 1, idx + n + 1, cmp);

        ans[n] = 1;
        for (int _ = 1; _ <= n; _++){
            int x = idx[_];
            if (dist[x] == -1) continue;
            for (PII& e: edge[x]){
                int y = e.first, w = e.second;
                if (dist[y] <= dist[x]) continue;
                ans[y] = (ans[y] + ans[x]) % MOD;
            }
        }

        return ans[1];
    }
};

   王希孟千里江山图卷