社区讨论

为什么自己手写的堆不如STL的priority_queue快

P2296[NOIP 2014 提高组] 寻找道路参与者 8已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mi5hr7r9
此快照首次捕获于
2025/11/19 12:17
4 个月前
此快照最后确认于
2025/11/19 12:17
4 个月前
查看原帖
手写堆如下:
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define INF 10000000
#define MAX_SIZE 1000000
using namespace std;
struct edge{
    int to,pre;
}e[200010];
int h[10010];
bool g[10010][10010];
bool vis[10010];
bool to_end[10010];
int dis[10010];
struct node{
    int from,dis;
    bool operator<(const node &n)const
    {
        return dis>n.dis;
    }
};
template<typename Tp>
class heap{
private: Tp arr[MAX_SIZE+10];
CPP
    int size;
public:
CPP
        heap()
        {
            memset(arr,0,sizeof(arr));
            size=0;
        }
        heap(const Tp* &a,const int &sz)
        {
            for(int i=1;i<=sz;i++)
                arr[i]=a[i];
            size=sz;
        }
        inline bool empty()
        {
            return size?false:true;
        }
        inline void push(const Tp &val)
        {
            arr[++size]=val;
            int i=size;
            while(i/2&&arr[i/2]<arr[i])
            {
                swap(arr[i],arr[i/2]);
                i/=2;
            }
        }
        inline Tp top()
        {
            if(size==0) printf("NO TOP\n");
            return arr[1];
        }
        inline void pop()
        {
            swap(arr[1],arr[size]);
            size--;int i=1,maxk;
            while(i<=size)
            {
                maxk=i;
                if(i*2<=size&&arr[maxk]<arr[i*2]) maxk=2*i;
                if(i*2+1<=size&&arr[maxk]<arr[i*2+1]) maxk=2*i+1;
                if(maxk==i) break;
                swap(arr[i],arr[maxk]);i=maxk;
            }
        }
        inline void make_heap(Tp *a,const int &sz)
        {
            size=sz;
            for(int i=1;i<=sz;i++)
                push(a[i]);
        }
        inline void clear()
        {
            size=0;
        }
};
heap<node> q;
int n,m,u,s,t;
inline void turn_dfs(const int &t)
{
    for(int i=1;i<=n;i++)
        if(!to_end[i]&&g[i][t])
        {
            to_end[i]=true;
            turn_dfs(i);
        }
}
inline bool off_road(const int &x)
{
    for(int i=h[x];i;i=e[i].pre)
        if(!to_end[e[i].to]) return true;
    return false;
}
int main()
{
    bool f=false;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&e[i].to);
        e[i].pre=h[u];h[u]=i;
        g[u][e[i].to]=true;
    }
    scanf("%d%d",&s,&t);
    to_end[t]=true;turn_dfs(t);
    for(int i=1;i<=n;i++)
        vis[i]=off_road(i);
    if(vis[s]==true||vis[t]==true) goto loop;
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    dis[s]=0;q.push((node){s,0});
    while(!q.empty())
    {
        node x=q.top();q.pop();
        int u=x.from;
        if(vis[u]) continue;
        vis[u]=true;
        if(u==t)
        {
            f=true;
            break;
        }
        for(int i=h[u];i;i=e[i].pre)
            if(!vis[e[i].to]&&dis[e[i].to]>dis[u]+1)
            {
                dis[e[i].to]=dis[u]+1;
                q.push((node){e[i].to,dis[e[i].to]});
            }
    }
    loop:;
    if(f) printf("%d\n",dis[t]);
    else printf("-1\n");
    return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...