链式前向星存图

dijkstra算法

堆优化

#include<iostream>
#include<cstring>
using namespace std;

const int maxn=1e4+3,maxm=1e5*5+3;
int n,m,s;
int h[maxn],v[maxm],w[maxm],nt[maxm],newnod=1;
int mindis[maxn];
bool book[maxn];

void push(int x,int y,int o){
	v[newnod]=y;
	w[newnod]=o;
	nt[newnod]=h[x];
	h[x]=newnod++;
}

struct nod{
	int v;
	int w;
};

bool operator <= (nod a,nod b){
	return a.w<=b.w;
}
bool operator < (nod a,nod b){
	return a.w<b.w;
}

class heaps{
private:
	nod heap[maxm];
	int t;
public:
	heaps(){
		t=0;
	}
	void siftup(int x){
		while(x>1){
			if(heap[x/2]<=heap[x])return;
			swap(heap[x/2],heap[x]);
			x/=2;
		}
		return;
	}
	void siftdown(int x){
		int now=x;
		while(x*2<=t){
			if(heap[x*2]<heap[now])now=x*2;
			if(x*2+1<=t and heap[x*2+1]<heap[now])now=x*2+1;
			if(now==x)return;
			swap(heap[now],heap[x]);
			x=now;
		}
		return;
	}
	void push(int v_in,int w_in){
		t++;
		heap[t].v=v_in;
		heap[t].w=w_in;
		siftup(t);
		return;
	}
	nod pop(){
		nod mem=heap[1];
		heap[1]=heap[t];
		t--;
		siftdown(1);
		return mem;
	}
}theheap;

int main(){
	memset(mindis,0x3f,sizeof mindis);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,o;
		cin>>x>>y>>o;
		push(x,y,o);
	}
	mindis[s]=0;
	theheap.push(s,0);
	//dijkstra
	for(int k=1;k<=n;k++){
		//1.find x_min
		nod now;
		do{
			now=theheap.pop();
		}while(book[now.v]);
		int x=now.v;
		book[x]=true;
		//2.songchi
		for(int i=h[x];i;i=nt[i]){
			if(!book[v[i]] and mindis[v[i]]>mindis[x]+w[i]){
				mindis[v[i]]=mindis[x]+w[i];
				theheap.push(v[i],w[i]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(mindis[i]==0x3f3f3f3f){
			cout<<0x7fffffff<<' ';
		}else cout<<mindis[i]<<' ';
	}
	return 0;
}