tle2,3,6求解
查看原帖
tle2,3,6求解
1122530
elpsconr楼主2024/4/8 01:49

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;
}
2024/4/8 01:49
加载中...