题解 P3371 【【模板】单源最短路径（弱化版）】

· · 题解

这题正解是SPFA，dij什么的都是秀
以上瞎扯，不用管。
简单介绍一下SPFA：先把所有点的值赋为INF，然后找到起点，标位零，将其压入队列（都到这里了，应该没人不会队列了吧…），下面的步骤要循环经行，直到队列为空。找到延生出来的节点，如果节点的值大于当前的点的值加边的长度（设当前节点的值是v_i，延伸出来的点的值是v_j，边的长度是d_i，则上面那句话的意思是如果v_i+d_i>v_j），就更新并加入队列。
具体实现就是这个亚子：

看到第三幅图的那个箭头了吗？那里是不能加入队列的，因为队列里已经有4号点了，这是SPFA最容易打错的地方。

（图片来源与洛谷2019夏令营的课件）
这里再说一下有关SPFA的其他的东西：

  1. 上面更新点的最短路的操作称为松弛操作

接下来是最激动人心的时刻：上代码！！！

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
queue<int>q;//系统自带队列，不懂的看底下
vector<int>g[200005];//同上
vector<int>dis[200005];
bool f[100005];//用于标记是否加入队列
int v[100005];//每个点离起点的最短路径
int main()
{
    cin>>n>>m>>s;
    for(register int i=1;i<=m;i++)
    {
        int ff,tt,dd;
        cin>>ff>>tt>>dd;
        g[ff].push_back(tt);
        dis[ff].push_back(dd);//建图
    }
    for(int i=1;i<=n;++i) v[i]=1e10;//初始化，SPFA的初始化必须是一个很大的值，因为它要处理负权边
    v[s]=0;
    f[s]=true;
    q.push(s);//压入起点
    while(!q.empty())//直到队列为空为止
    {
        int xx=q.front();q.pop();//取出第一个元素并弹出
        f[xx]=false;//标记为没有加入队列
        for(register int i=0;i<g[xx].size();i++)//该节点延伸出来的点
         if(v[g[xx][i]]>v[xx]+dis[xx][i])//松弛操作
         {
             if(!f[g[xx][i]]) q.push(g[xx][i]),f[g[xx][i]]=true;//加入队列
             v[g[xx][i]]=v[xx]+dis[xx][i];//更新
         }
    }
    for(register int i=1;i<=n;i++)
     if(v[i]!=1e10) cout<<v[i]<<' ';
     else cout<<"2147483647"<<' ';
    return 0;
}

附：queue vector 以及 本蒟蒻的博客