tle三个点,求改进优化dijkstra堆优化的方式。
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int N=2e5+6;
int n,m,s,idx;
int e[N<<1],h[N],w[N<<1],ans[N],ne[N<<1];
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void dijkstra(int x)
{
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,x});st[x]=1;
while(!q.empty())
{
int ww=q.top().second;q.pop();
for(int i=h[ww];~i;i=ne[i])
{
int j=e[i];
if(ww==j) continue;
if(ans[j]>ans[ww]+w[i])
{
ans[j]=ans[ww]+w[i];
if(!st[j]) q.push({ans[j],j});
}
}
}
}
int main()
{
memset(ans,0x3f,sizeof ans);
memset(st,0,sizeof st);
memset(h,-1,sizeof h);
cin>>n>>m>>s;
ans[s]=0;
for(int i=1;i<=m;++i)
{
int u,v,r;cin>>u>>v>>r;
add(u,v,r);
}
dijkstra(s);
for(int i=1;i<=n;++i)
cout<<ans[i]<<" ";
return 0;
}