社区讨论
为什么自己手写的堆不如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 条回复,欢迎继续交流。
正在加载回复...