模板合集

第一个是堆模板，堆顶为最大或者最小的那个值，具体是大还是小，取决于个人，二叉堆的原理主要是，如下是个小根堆

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int heap[2000005],siz,n;
void push(int x){
	heap[++siz]=x;
	int now=siz;
	while(now){
		if(heap[now]<heap[now>>1])
			swap(heap[now],heap[now>>1]);
		else break;
		now>>=1;
	}
}
void pop(){
	swap(heap[siz],heap[1]);
	siz--;
	int now=1;
	while((now<<1)<=siz){
		int nxt=now<<1;
		if(nxt+1<=siz&&heap[nxt+1]<heap[nxt]) nxt++;
		if(heap[nxt]<heap[now]) swap(heap[nxt],heap[now]);
		else break;
		now=nxt;
	}
}
int main(){
	//heap[0]=-9999999;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int x;
			scanf("%d",&x);
			push(x);
		}
		if(opt==2) printf("%d\n",heap[1]);
		if(opt==3) pop();
	}
	return 0;
}

第二个模板是单源最短路径dijkstra的求法，具体方法就是每次找到距离源点最近的点往周围扩张，最后直至遍历整个图，上代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define pa pair<int,int>
#define MAXN 500005
using namespace std;
priority_queue<pa,vector<pa>,greater<pa> >q;
int head[MAXN],nxt[MAXN],to[MAXN],val[MAXN],ce,n,m,d[MAXN],t;
bool used[MAXN];
void add(int u,int v,int w){
	to[++ce]=v,nxt[ce]=head[u],head[u]=ce,val[ce]=w;
}
void dij(){
	memset(d,0x3f,sizeof(d));
	q.push(make_pair(0,t));
	d[t]=0;
	while(q.size()){
		int u=q.top().second;
		q.pop();
		if(used[u]) continue;
		used[u]=1;
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(d[v]>d[u]+val[i]){
				d[v]=d[u]+val[i];
				q.push(make_pair(d[v],v));
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dij();
	for(int i=1;i<=n;i++)
		if(used[i]) printf("%d ",d[i]);
		else printf("2147483647 ");
	return 0;
}