Dijkstra堆优化32pts求调

P4779 【模板】单源最短路径(标准版)

hhhh2971 @ 2024-08-14 14:02:08

测试点1 、 3 、 4WA,测试点6TLE

#include<bits/stdc++.h>
using namespace std;

const long long inf=2147483647;

long long u[5000005],v[5000005],c[5000005];
long long cnt;
bool vis[1000005];
long long first[1000005],nxt[1000005];
long long dis[1000005];
long long pos[1000005];
struct Node
{
    long long diss,hao;
}heap[10000005];

void siftdown(long long i)
{
    long long temp=i;
    bool cmp=false;
    while (i*2<=cnt && !cmp)
    {
        if (heap[i].diss>heap[i*2].diss) temp=i*2;
        if (i*2+1<=cnt)
            if (heap[temp].diss>heap[i*2+1].diss) temp=i*2+1;
        if (temp!=i)
        {
            swap(pos[heap[temp].hao],pos[heap[i].hao]);
            swap(heap[temp],heap[i]);
            i=temp;
        }
        else cmp=true;
    }
}

void siftup(long long i)
{
    if (i==1) return;
    bool cmp=false;
    while (i!=1 && !cmp)
    {
        if (heap[i].diss<heap[i/2].diss)
        {
            swap(pos[heap[i].hao],pos[heap[i/2].hao]);
            swap(heap[i],heap[i/2]);
        }
        else cmp=true;
        i=i/2;
    }
}

void popp()
{
    swap(pos[heap[1].hao],pos[heap[cnt].hao]);
    swap(heap[1],heap[cnt]);
    pos[heap[cnt].hao]=0;
    heap[cnt].diss=0;
    heap[cnt].hao=0;
    cnt--;
    siftdown(1);
}

void pushh(long long x)
{
    cnt++;
    pos[x]=cnt;
    heap[cnt].hao=x;
    heap[cnt].diss=dis[x];
    siftup(cnt);
}

long long topp()
{
    return heap[1].hao;
}

int main()
{
    long long n,m,s;
    cin >> n >> m >> s;
    for (long long i=1;i<=n;i++)
        first[i]=-1;
    for (long long i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u[i],&v[i],&c[i]);
        nxt[i]=first[u[i]];
        first[u[i]]=i;
    }
    for (long long i=1;i<=n;i++)
        dis[i]=inf;
    dis[s]=0;
    cnt=0;
    pushh(s);
    for (long long i=1;i<=n;i++)
    {
        long long ans;
        ans=topp();
        popp();
        vis[ans]=true;
        long long k=first[ans];
        while (k!=-1)
        {
            if (!vis[v[k]] && dis[v[k]]>dis[u[k]]+c[k])
            {
                dis[v[k]]=dis[u[k]]+c[k];
                if (!pos[v[k]]) pushh(v[k]);
                else pushh(v[k]);
            }
            k=nxt[k];
        }
    }
    for (long long i=1;i<=n;i++)
        cout << dis[i] << " ";

    return 0;
}

by cj180202 @ 2024-08-14 14:17:28

手写堆改掉!用优先队列

效率开了 O2 基本没有差别,手写就是作。


by cj180202 @ 2024-08-14 14:17:44

@hhhh2971


by hhhh2971 @ 2024-08-14 15:50:36

@cj180202 好的,谢谢dalao


|