提交结果

代码：

#include<bits/stdc++.h>
#define INF 99999999
using namespace std;
long long i,j,n,m,s,u,v,w,flag[500005],dis[500005],e[1005][1005];
long long min_d;
long long U;
void Dijkstra()
{
	for(i=1;i<=n-1;i++)
	{
		min_d=INF;
		for(j=1;j<=n;j++)
		{
			if(flag[j]==0&&dis[j]<min_d)
			{
				min_d=dis[j];
				U=j;
			}
		}
		flag[U]=1;
		for(j=1;j<=n;j++)
		{
			if(e[U][j]<INF)
			{
				if(dis[j]>dis[U]+e[U][j])
					dis[j]=dis[U]+e[U][j];
			}
		} 
	}
}
int main()
{
	cin>>n>>m>>s;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				e[i][j]=0;
			else
				e[i][j]=INF;
	for(i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		e[u][v]=w;
	}
	for(i=1;i<=n;i++)
		dis[i]=e[s][i];
	for(i=1;i<=n;i++)
		flag[i]=0;
	flag[s]=1;
	Dijkstra();
	for(i=1;i<=n;i++)
		cout<<dis[i]<<' ';
	return 0;
}