在記錄優(yōu)化之前，先要知道使用一個(gè)類(lèi)模板—優(yōu)先隊(duì)列(stl):

STL中定義優(yōu)先隊(duì)列的模板類(lèi)為priority_queue，其定義如下：
templateclass priority_queue;
模板里面有三個(gè)參數(shù)，第一個(gè)為元素的類(lèi)型，第二個(gè)為所使用的容器（vector或deque），第三個(gè)為一個(gè)比較的規(guī)則，決定是大優(yōu)先隊(duì)列還是最小優(yōu)先隊(duì)列，默認(rèn)的less為大優(yōu)先隊(duì)列，實(shí)現(xiàn)方式是大堆，greater為最小優(yōu)先隊(duì)列，實(shí)現(xiàn)方式是最小堆，結(jié)構(gòu)都是二叉樹(shù)。

大根堆就是根節(jié)點(diǎn)大，小根堆就是根節(jié)點(diǎn)最小。

#include//c++標(biāo)準(zhǔn)頭文件，可以使用cout,cin等標(biāo)準(zhǔn)庫(kù)函數(shù) 
#include//使用priority_queue時(shí)需要的頭文件 
using namespace std;//命名空間，防止重名給程序帶來(lái)各種隱患，使用cin,cout,stack,map,set,vector,queue時(shí)都要使用
struct test {//定義一個(gè)結(jié)構(gòu)體test 
	int val;
	test(int v) {//構(gòu)造函數(shù) 
		this->val = v;
	}
	bool operator >(const test t)const {//重載運(yùn)算符>if (val >t.val)
			return true;
		else
			return false;
	}
	bool operator< (const test t)const {//重載運(yùn)算符
		return val< t.val;
	}
};
int main() {priority_queue, less>q1;//定義一個(gè)大頂堆q1 
	cout<< "定義一個(gè)大根堆q1: priority_queue,less>q1"<< endl;
	q1.push(test(10));//向隊(duì)列中添加一個(gè)test，val的值為10 
	q1.push(test(5));//向隊(duì)列中添加一個(gè)test，val的值為5
	q1.push(test(7));//向隊(duì)列中添加一個(gè)test，val的值為7
	cout<< "按順序添加val的值為10、5、7的test,目前隊(duì)列的元素：test(10) test(5) test(7)"<< endl;
	cout<< "q1.top().val="<< q1.top().val<< endl;
	cout<< endl;


	q1.pop();
	cout<< "q1.pop()后，目前隊(duì)列的元素：test(5) test(7)"<< endl;
	cout<< "q1.top().val="<< q1.top().val<< endl;
	cout<< endl;


	q1.pop();
	cout<< "q1.pop()后，目前隊(duì)列的元素：test(5)"<< endl;
	cout<< "q1.top().val="<< q1.top().val<< endl;
	cout<< endl;

	q1.pop();
	cout<< "q1.pop()后，目前隊(duì)列是空的"<< endl;
	cout<< "目前隊(duì)列是空的，不能使用q1.top()查詢(xún)隊(duì)首元素"<< endl;
	cout<< endl<< endl;



	priority_queue, greater>q2;//定義一個(gè)大頂堆q1 
	cout<< "定義一個(gè)小根堆q2: priority_queue,greate>q2"<< endl;
	q2.push(test(10));//向隊(duì)列中添加一個(gè)test，val的值為10 
	q2.push(test(5));//向隊(duì)列中添加一個(gè)test，val的值為5
	q2.push(test(7));//向隊(duì)列中添加一個(gè)test，val的值為7
	cout<< "按順序添加val的值為10、5、7的test,目前隊(duì)列的元素：test(10) test(5) test(7)"<< endl;
	cout<< "q2.top().val="<< q2.top().val<< endl;
	cout<< endl;


	q2.pop();
	cout<< "q2.pop()后，目前隊(duì)列的元素：test(10) test(7)"<< endl;
	cout<< "q2.top().val="<< q2.top().val<< endl;
	cout<< endl;


	q2.pop();
	cout<< "q2.pop()后，目前隊(duì)列的元素：test(10)"<< endl;
	cout<< "q2.top().val="<< q2.top().val<< endl;
	cout<< endl;

	q2.pop();
	cout<< "q1.pop()后，目前隊(duì)列是空的"<< endl;
	cout<< "目前隊(duì)列是空的，不能使用q2.top()查詢(xún)隊(duì)首元素"<< endl;


}

題目：dijkstra優(yōu)化

#include#include#include#includeusing namespace std;
const int N=150010,M=N*2,INF=0x3f3f3f3f;
typedef pairPII;
int head[N],e[N],ne[N],w[N];
int dist[N],st[N];
int idx,n,m;

void add(int a,int b,int c)
{e[idx]=b;
	w[idx]=c;
	ne[idx]=head[a];
	head[a]=idx++;
}

int dijkstra()
{memset(dist,INF,sizeof dist);
	dist[1]=0;
	priority_queue,greater>heap;
	heap.push({0,1});
	while(heap.size())
	{PII k=heap.top();
		heap.pop();
		int distance=k.first,ver=k.second;
		if(st[ver]==1)continue;
		else st[ver]=1;
		for(int i=head[ver];i!=-1;i=ne[i])
		{	int j=e[i];
			if(st[j]==0&&dist[j]>distance+w[i])
			{		dist[j]=distance+w[i];
				heap.push({dist[j],j});
			}
		}
	}
	if(dist[n]==INF)return -1;
	else return dist[n];
}
int main()
{cin>>n>>m;
	memset(head,-1,sizeof head);
	for(int i=0;iint a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	cout<

#include#include#include
using namespace std;
const int N=100010;
struct edge
{int a,b,w;
}edge[N];
int dist[N];
int backup[N];
int n,m,k;

int bellman_ford()
{memset(dist,0x3f3f3f3f,sizeof dist);
	dist[1]=0;
	for(int i=1;i<=k;i++)
	{memcpy(backup,dist,sizeof dist);
		for(int j=1;j<=m;j++)
		{	int a=edge[j].a,b=edge[j].b,w=edge[j].w;
			dist[b]=min(dist[b],backup[a]+w);
		}
	}
	return dist[n];
}


int main()
{cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{int a,b,c;
		cin>>a>>b>>c;
		edge[i].a=a,edge[i].b=b,edge[i].w=c;
	}
	
	int t=bellman_ford();
	if(t>=0x3f3f3f3f/2)cout<<"impossible";
	else cout<

#include#include#include
#includeusing namespace std;
const int N=1e5+10;
int head[N],e[N],ne[N],w[N],idx;
int dist[N],st[N];
int n,m;

void add(int a,int b,int c)
{e[idx]=b,ne[idx]=head[a],w[idx]=c,head[a]=idx++;
}

void spaf()
{queueq;
	q.push(1);
	dist[1]=0;
	st[1]=1;
	while(!q.empty())
	{		int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=head[t];i!=-1;i=ne[i])
		{	int a=e[i],b=w[i];
			if(dist[a]>dist[t]+b)
			{		dist[a]=dist[t]+b;
				if(st[a]==0)
				{st[a]=1;
					q.push(a);
				}
			}
		}
	}	
}

int main()
{cin>>n>>m;
	memset(head,-1,sizeof head);
	memset(dist,0x3f,sizeof dist);
	for(int i=0;iint a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	spaf();
	if(dist[n]==0x3f3f3f3f)
		cout<<"impossible";
	else
		cout<

#include#include#include
#includeusing namespace std;
const int N=1e4+10;

int head[N],e[N],ne[N],w[N],idx;
int st[N],cnt[N],dist[N];
int n,m;

void add(int a,int b,int c)
{e[idx]=b,ne[idx]=head[a],w[idx]=c,head[a]=idx++;
}

bool spaf()
{queueq;
	for(int i=1;i<=n;i++)
	{q.push(i);
		st[i]=1;
	}
	dist[1]=0;
	while(!q.empty())
	{int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=head[t];i!=-1;i=ne[i])
		{	int j=e[i],k=w[i];
			if(dist[j]>dist[t]+k)
			{		dist[j]=dist[t]+k;
				cnt[j]++;
				if(cnt[j]>m)
					return true;
				if(st[j]==0)
				{st[j]=1;
					q.push(j);
				}
			}
		}
	}
	return false;
}

int main()
{cin>>n>>m;
	memset(head,-1,sizeof head);
	memset(dist,0x3f,sizeof dist);
	for(int i=0;iint a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	if(spaf())
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}