东方博宜OJ2416 - 最短路和负环 题目描述 给出一个有 NN 个节点，MM 条边的带权有向图。

要求你写一个程序， 判断这个有向图中是否存在负权回路。 如果从一个点沿着某条路径出发， 又回到了自己， 而且所经过的边上的权和小于00， 就说这条路是一个负权回路。如果存在负权回路， 只输出一行-1−1；

如果不存在负权回路， 再求出一个点 SS (1≤S≤N1≤S≤N)到每个点的最短路的长度。 约定： SS 到 SS 的距离为 00 , 如果 SS 与这个点不连通, 则输出NoPath。

输入 第一行：点数 NN (2≤N≤10002≤N≤1000)，边数 MM (1≤M≤10001≤M≤1000)，源点 SS (1≤S≤N1≤S≤N);

以下 MM 行, 每行三个整数 aa, bb, cc 表示点aa, bb(1≤a, b≤N1≤a,b≤N)之间连有一条边, 权值为 cc (-1,000,000≤c≤1,000,000−1,000,000≤c≤1,000,000) 请注意：本题两点之间可能存在多条边。

输出 如果存在负权环， 只输出一行-1−1。

如果不存在负环，请按如下要求输出：

共 NN 行， 第 ii 行描述 SS 点到 ii 点的最短路: 如果 SS 与 ii 不连通, 输出NoPath; 如果 i = Si=S, 输出 00;

其他情况输出 SS 到 ii 的最短路的长度。

样例

输入

6 8 1 1 3 4 1 2 6 3 4 -7 6 4 2 2 4 5 3 6 3 4 5 1 3 5 4

输出

0 6 4 -3 -2 7

#include<bits/stdc++.h>
#define int long long
const int N=1e6+10,INF=100000000000;
using namespace std;
struct node
{
	int nextt,to,q;
}e[N];
queue<int>q;
int h[N],cnt,d[N],n,m,t[N],s;
void add(int u,int v, int w)
{
	e[++cnt].to=v;
	e[cnt].q=w;
	e[cnt].nextt=h[u];
	h[u]=cnt;
}
bool v[N];
void spfa(int s)
{
	for(int i=1;i<=n;i++)
	{
		q.push(i);
		v[i]=1;
	}
	for(int i=1;i<=n;i++)d[i]=INF;
	d[s]=0;
	while(!q.empty())
	{
		int k=q.front();
		v[k]=0;
		q.pop();
		for(int i=h[k];i;i=e[i].nextt)
		{
			if(d[e[i].to]>d[k]+e[i].q)
			{
				d[e[i].to]=d[k]+e[i].q;
				t[e[i].to]=t[k]+1;
				if(!v[e[i].to])
				{
					q.push(e[i].to);
					v[e[i].to]=1;
				}
			}
		}
	} 
}
bool SPFA(int s)
{
	for(int i=1;i<=n;i++)v[i]=0;
	while(!q.empty())q.pop( );
	for(int i=1;i<=n;i++)
	{
		q.push(i);
		v[i]=1;
	}
	v[s]=1;
	q.push(s);
	for(int i=1;i<=n;i++)d[i]=INF;
	d[s]=0;
	while(q.empty()==false)
	{
		int k=q.front();
		v[k]=0;
		q.pop();
		for(int i=h[k];i;i=e[i].nextt)
		{
			if(d[e[i].to]>d[k]+e[i].q)
			{
				d[e[i].to]=d[k]+e[i].q;
				t[e[i].to]=t[k]+1;
				if(t[e[i].to]>=n)return false;
				if(!v[e[i].to])
				{
					q.push(e[i].to);
					v[e[i].to]=1;
				}
			}
		}
	}
	return true;
}
signed main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	if(SPFA(s))
	{
		spfa(s);
		for(int i=1;i<=n;i++)
		{
			if(i==s)
			{
				cout<<"0"<<endl;
				continue;
			}
			if(d[i]==INF)
			{
				cout<<"NoPath"<<endl;
				continue;
			}
			cout<<d[i]<<endl;
		}
	}
	else
	{
		cout<<"-1";
		return 0;
	}
	return 0;
}