SLF -> Small Label First

SPFA-> Shortest Path Faster Algorithm

更通用的说法是Queue Optimized Bellman-Ford

#include<cstdio>
#include<stack>
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#define int long long
using namespace std;
int dis[100004],n,m,s;
bool vis[100004];
vector<pair<int,int> >G[100004];
int read() {
    int x=0,f=1;
    char ch;
    do {
        ch=getchar();
        if(ch=='-')f=-1;
    } while(ch<'0'||ch>'9');
    do {
        x=10*x+ch-'0';
        ch=getchar();
    } while(ch>='0'&&ch<='9');
    return f*x;
}
void spfa(int S) {
    deque<int>q;//SLF对于一个要加入的点u,如果dis[u]<dis[Q.front()],u就放入队首,否则放入队尾。
    q.push_back(S);
    for(int i=1; i<=n; i++)dis[i]=0x7ffffff;
    dis[S]=0;
    while(!q.empty()) {
        int x=q.front();
        q.pop_front();
        vis[x]=0;
        int sz=G[x].size();
        for(int i=0; i<sz; i++) {
            int y=G[x][i].first,w=G[x][i].second;
            if(dis[y]>dis[x]+w) {
                dis[y]=dis[x]+w;
                if(!vis[y]) {
                    vis[y]=1;
                    if(dis[y]<dis[q.front()])q.push_front(y);
                    else q.push_back(y);
                }
            }
        }
    }
}
signed main() {
    n=read(),m=read(),s=read();
    for(int i=1; i<=m; i++) {
        int x=read(),y=read(),z=read();
        G[x].push_back(make_pair(y,z));
    }
    spfa(s);
    for(int i=1; i<=n; i++)if(dis[i]!=0x7ffffff)printf("%lld ",dis[i]);
        else printf("%lld ",INT_MAX);
    return 0;
}

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类