T飞了

两遍 dijk 做法,还有啥优化吗

#include<bits/stdc++.h>
using namespace std;
int n,m;
int h[1145140],ne[1145140],e[1145140],w[11451410],idx;
int d[1145140];
bool st[1145140];
long long ans;
priority_queue<pair<int,int>> q;
int hh[1145140],nne[1145140],ee[1145140],ww[11451410],idxx;
int dd[1145140];
bool stt[1145140];
priority_queue<pair<int,int>> qq;
void addd(int a,int b,int c)
{
    idxx++;
    nne[idx]=h[a];
    ee[idx]=b;
    ww[idx]=c;
    hh[a]=idxx;
}

void add(int a,int b,int c)
{
    idx++;
    ne[idx]=h[a];
    e[idx]=b;
    w[idx]=c;
    h[a]=idx;
}

void dijk()
{
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(st[x])
          continue;
        st[x]=1;
        for(int i=h[x];i;i=ne[i])
        {
            int y=e[i],z=w[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }  

    } 

}
void dijkk()
{
    qq.push(make_pair(0,1));
    while(qq.size())
    {
        int x=qq.top().second;
        qq.pop();
        if(stt[x])
          continue;
        stt[x]=1;
        for(int i=hh[x];i;i=nne[i])
        {
            int y=ee[i],z=ww[i];
            if(dd[y]>dd[x]+z)
            {
                dd[y]=dd[x]+z;
                qq.push(make_pair(-dd[y],y));
            }
        }  

    } 

}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    memset(d,0x3f,sizeof d);
    memset(dd,0x3f,sizeof dd);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(b,a,c);
        addd(a,b,c);
    }

    d[1]=0;
    dd[1]=0;
    dijk();
    dijkk();
    for(int i=1;i<=n;i++)
      ans+=d[i]+dd[i]; 

    cout<<ans;

    return 0;
 }