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;
}

No responses yet