提交记录

#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN=10010,MAXM=500010;
const ll INF=(1<<31)-1;
ll n,m,s,head[MAXN],dis[MAXN],cnt;
bool vis[MAXN];
struct EDGE
{
	ll v,w,nxt;
}edge[MAXM];
struct node
{
	ll u,dis;
	bool operator<(node a)const
	{
		return dis>a.dis;
	}
};
priority_queue<node> q;
void add(ll u,ll v,ll w)
{
	cnt++;//增加一条边
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
void dijkstra(ll sn)//初始节点 
{
	dis[sn]=0;//孤岛第一个节点到自己距离为0
	vis[sn]=true;//已访问过 
	//在孤岛第一个节点开始松弛
	for(ll i=head[sn];i;i=edge[i].nxt)
	{
		ll v=edge[i].v,w=edge[i].w;
		dis[v]=w;//由于初始距离无限大,所以目前为初始节点通过该一边到其的距离 
		q.push((node){v,dis[v]});//存入堆 
	} 
	while(!q.empty())//反复扩展孤岛进行松弛 
	{
		ll u=q.top().u;//取出最近的节点 
		q.pop();
		if(vis[u]) continue;//如已在孤岛中跳过 
		vis[u]=true;//节点加入孤岛
		for(ll i=head[u];i;i=edge[i].nxt)//对边进行松弛 
		{
			ll v=edge[i].v,w=edge[i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push((node){v,dis[v]});//添加入堆,寻找最近的节点 
			}
		} 
	}
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&s);
	for(ll i=1;i<=n;i++)
	{
		dis[i]=INF;//初始值无限大,后松弛 
	}
	ll u,v,w;
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);//添加有向边 
	}
	dijkstra(s);//dijkstra求最短路
	//输出部分
	for(ll i=1;i<=n;i++)
	{
		printf("%lld ",dis[i]);
	} 
	return 0;
}