RT
题目

#include<bits/stdc++.h>
#define int __int128
using namespace std;
int inf=2e24+10;
int n,m,st,x,y,z,dis[2010];
struct edge{int x,y,z;}e[5010];
inline int read()
{
	char c=getchar();
	int x=0,s=1; 
	while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*s;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
void bellman()
{
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[st]=0;
	for(int i=1;i<=n*2;i++)
		for(int j=1;j<=m;j++)
			dis[e[j].y]=min(dis[e[j].y],dis[e[j].x]+e[j].z);
	for(int i=1;i<=m;i++)if(dis[e[i].y]>dis[e[i].x]+e[i].z)dis[e[i].y]=-inf;
}
signed main()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	n=read(),m=read(),st=read();
	for(int i=1;i<=m;i++)	e[i].x=read(),e[i].y=read(),e[i].z=read();
	bellman();
	for(int i=1;i<=n;i++)
	{    	
		if(dis[i]==-inf)putchar('-');
		else if(dis[i]==inf)putchar('*');
		else write(dis[i]);
		putchar('\n');
	}
	return 0;
}