【Luogu P4779】dijkstra算法的堆优化

Luogu P4779

利用堆/优先队列快速取得权值最小的点。

在稠密图中的表现比SPFA要优秀。

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

struct data

{

	long long next,to,val;

}edge[500005];

long long cnt,head[500005],n,m,s,u,v,w,cost[500005];

bool vis[500005];

struct node

{

	long long id,val;

	bool operator < (const node&x) const

	{

		return val>x.val;

	}

};

priority_queue<node> que;

void add(long long sta,long long to,long long val)

{

	edge[++cnt].to=to;

	edge[cnt].val=val;

	edge[cnt].next=head[sta];

	head[sta]=cnt;

}

int main()

{

	scanf("%lld%lld%lld",&n,&m,&s);

	for (int i=1;i<=m;i++)

	{

		scanf("%lld%lld%lld",&u,&v,&w);

		add(u,v,w);

	}

	for (int i=1;i<=n;i++) cost[i]=214748364700000000;

	cost[s]=0;

	node tmp;

	tmp.id=s;tmp.val=cost[s];

	que.push(tmp);

	while (!que.empty())

	{

		node minp=que.top();

		que.pop();

		if (vis[minp.id]) continue;

		vis[minp.id]=true;

		for (int j=head[minp.id];j;j=edge[j].next)

		{

			long long tmpv=edge[j].to,tmpw=edge[j].val;

			if (cost[tmpv]>tmpw+minp.val)

			{

				cost[tmpv]=tmpw+minp.val;

				tmp.val=cost[tmpv];

				tmp.id=tmpv;

				que.push(tmp);

			}

		}

	}

	for (int i=1;i<=n;i++) printf("%lld ",cost[i]);

	return 0;

}

巴特西

【Luogu P4779】dijkstra算法的堆优化

最新文章

热门文章