图论:SPFA算法

例题:点击这里

#include <cstdio>
#include <cstring>
#include <vector>
#include<queue>
#include<iostream>
#include <algorithm>
using namespace std;
const long long inf=2147483647;
#define maxd 10000+5
#define maxm 500000+5
struct Edge{
	int to,next,w;
}edge[maxm];
int n,m,s;
int head[maxd];//链式前向星 
int dis[maxd];//距离 
bool inqueue[maxd];//是否在队列中 
int fu[maxd];//判断负圈 
int pre[maxd];//记录路径 
int edge_num=0;
void addedge(int u,int v,int w){
	edge[edge_num].to=v;
	edge[edge_num].w=w;
	edge[edge_num].next=head[u];
	head[u]=edge_num++;	
}
int spfa(int s){
	memset(fu,0,sizeof(fu));
	fu[s]=1;
	for(int i=0;i<maxd;i++){
		dis[i]=inf;
		inqueue[i]=false;
	}
	dis[s]=0;
	queue<int>q;
	q.push(s);
	inqueue[s]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inqueue[u]=false;
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			int w=edge[i].w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				pre[v]=u;
				if(!inqueue[v]){
					inqueue[v]=true;
					q.push(v);
					fu[v]++;
					if(fu[v]>n) return 1;
				}
			}
		}
	}
	return 0;
}
int main() {
	scanf("%d%d%d",&n,&m,&s);
	memset(head,-1,sizeof(head));
	for(int i=0;i<m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
	}
	spfa(s);
	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	return 0;
}