悬赏一个关注

60分提交记录3MLE1WA

#include<bits/stdc++.h>//shortest-path
#define sz 10005
#define inf 2147483647
using namespace std;
int n,m,s,dis[sz],done;
bool mark[sz];
map< pair<int,int> ,int>a;
map< pair<int,int> ,bool>con;
int main()
{
	memset(dis,0x3f,sizeof(dis));
	scanf("%d%d%d",&n,&m,&s);
	dis[s]=0;
	for(int i=1;i<=m;i++)
	{
		int u,v,len;
		scanf("%d%d%d",&u,&v,&len);
		if(u==v) continue;
		if(!a[ make_pair(u,v) ])a[ make_pair(u,v) ]=len;
		else a[ make_pair(u,v) ]=min(a[ make_pair(u,v) ],len);
		con[ make_pair(u,v) ]=1;
	}
	while(done<n)
	{
		int minn=inf,p=0;
		for(int i=1;i<=n;i++)
		{
			if(mark[i]) continue;
			if(dis[i]<minn) minn=dis[i],p=i;
		}
		mark[p]=1,done++;
		for(int j=1;j<=n;j++)//u=p,v=j
		{
			if(con[ make_pair(p,j) ])
			{
				dis[j]=min(dis[j],dis[p]+a[ make_pair(p,j) ]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i]<inf) printf("%d ",dis[i]);
		else printf("%d ",1<<31-1);
	} 
	return 0;
}