rt

堆优化+邻接表dijkstra 弱化版AC

#include <bits/stdc++.h>
using namespace std;
const long long int INF=(1<<31)-1;
int head[1000010];//左节点目录 
int ver[1000010];//右节点目录 
int edge[1000010];//边权值 
int nxt[1000010];//第一个与它相连的点的下标 
int tot;//邻接表节点个数 
int vis[1000010];//集合标记
int dis[1000010];//距离记录 
int n /*点*/,m /*边*/; 
int sta/*起点*/;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;/*第一维距离，第二维编号*/
inline void add(int x,int y,int z)//建邻接表 
{
	ver[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];//下一节点 
	head[x]=tot;
}
int main()
{
	cin>>n>>m>>sta;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dis[sta]=0;
	q.push(make_pair(0,sta));//首元素入队列 
	while(!q.empty())
	{
		int x=q.top().second;//利用优先队列（堆）直接找到最短dis的点 
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;//加入集合 
		for(int i=head[x];i;i=nxt[i])//链表遍历 
		{
			int y=ver[i],z=edge[i];
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				q.push(make_pair(dis[y],y));//更新元素入队 
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i]>=0x3f3f3f3f/2)
			cout<<INF<<" ";
		else cout<<dis[i]<<" ";
	}
	return 0;
}