单源最短路SPFA

佚名 6年前 (2019-04-09) 随笔 782人围观抢沙发百度已收录

前提：你要知道什么是最短路和什么是图。

下面代码注释已经很完全了，哪里不懂可以问我，我会进行改进

#include<bits/stdc++.h>
#define inf 2147483647              //下文的inf代替为2147483647
using namespace std;
const int maxn=500001;
queue<int>q;
int dis[maxn],vis[maxn],head[maxn],Next[maxn],from[maxn],to[maxn],cost[maxn],cnt;
int n,m,S,x,y,z;
void SPFA(int S)                    //SPFA，S为起点，求出从S出发的所有点的最短路 
{
    for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;   //初始dis无限大，经过点清0 
    vis[S]=1;dis[S]=0;q.push(S);    //压入起点 
    while(!q.empty())               //q队列为空退出 
    {
        int u=q.front();q.pop();    //对q队列的队头进行操作 ，u为队头 
        vis[u]=0;                   //将改点标记为不在队列 
        for(int i=head[u];i!=-1;i=Next[i])  //遍历以u为起点的所以边 
        {
            int v=to[i];            //v为改边到达的点 
            if(dis[v]>dis[u]+cost[i])   //如果从u经过i边比原先v最短路小就更新 
            {
                dis[v]=dis[u]+cost[i];  //更新 
                if(vis[v]==0)           //如果v不在队列 
                {
                    q.push(v);          //将v压入队列 
                    vis[v]=1;           //标记v在队列内 
                }
            }
        }
    }
    //跑完SPFA后，dis[i]为以S为起点，到i的最短路 
}
void add(int x,int y,int z)         //前向星建图 
{
    cnt++;                          //表示边数 
    from[cnt]=x;to[cnt]=y;          //from表示cnt边的出发点，to表示cnt边的到达点 
    Next[cnt]=head[x];              //Next指向上一条以x为起点的边
    head[x]=cnt;                    //head[x]表示以x为起点的最后输入的边的编号
    cost[cnt]=z;                    //经过cnt边的费用 
}
int main()
{
    memset(head,-1,sizeof(head));   //初始-1，其实是为边界 
    scanf("%d%d%d",&n,&m,&S);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);                 //对x到y，费用为z建一条边 
    }
    SPFA(S);                        //跑SPFA 
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);       //输出 
    }
}