Mars_Cat

这是一份SPFA模板

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

#define mp make_pair
#define pb push_back

int x,y,v;

int n,m;
int s,e;
queue<int> Q;
int dis[10010];
bool ninQ[10010];
vector<pair<int,int> > r[10010];

int main()
{
	memset(ninQ,1,sizeof(ninQ));
	memset(dis,0,sizeof(dis));
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i)
	{
		scanf("%d%d%d",&x,&y,&v);
		r[x].pb(mp(y,v));
	}
	Q.push(1);
	ninQ[false]=0; dis[1]=0;
	while(!Q.empty())
	{
		int xx=Q.front(); Q.pop(); ninQ[xx]=true;
		for(int i=0;i<r[xx].size();++i)
			if(r[xx][i].second+dis[xx]<dis[r[xx][i].first] || dis[r[xx][i].first]==0)
			{
				dis[r[xx][i].first]=r[xx][i].second+dis[xx];
				if(ninQ[r[xx][i].first])
				{
					Q.push(r[xx][i].first);
					ninQ[r[xx][i].first]=false;
				}
			}
	}
	for(int i=2;i<=n;++i)
		if(dis[i]!=0)
			printf("1->%d:%d\n",i,dis[i]);
		else printf("1->%d:XXXXX\n",i);
	return 0;
}