单源最短路-dijkstra+优先队列优化
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=5e5+10;
int n,m,s,bb=1;
int dis[N],vis[N];//vis为是否已成无法再次更新的点
struct node{
int x,y;
bool operator > (const node & a) const //重载运算符 ,x小才算小的
{
return x>a.x;
}
};
priority_queue<node,vector<node>,greater<node> > q;//优先队列优化
int tot=1,head[N],ver[M],edge[M],Next[M];//链式前向星存图
void add(int x,int y,int z)
{
ver[++tot]=y;
edge[tot]=z;
Next[tot]=head[x];
head[x]=tot;
}
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push({dis[s],s});
while(!q.empty())
{
int x=q.top().y;
q.pop();
if(vis[x])
continue;
vis[x]=1;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(!vis[y]&&dis[y]>dis[x]+edge[i])
{
dis[y]=dis[x]+edge[i];
q.push({dis[y],y});
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dijkstra();
for(int i=1;i<=31;i++)
bb*=2;
bb-=1;
for(int i=1;i<=n;i++)
{
if(dis[i]!=0x3f3f3f3f)
printf("%d ",dis[i]);
else
printf("%d ",bb);
}
return 0;
}
标签:10,head,考前,int,tot,vis,模板,dis
From: https://www.cnblogs.com/kezhuo/p/16626472.html