模板题---2.1（图论)-创新互联

在记录优化之前，先要知道使用一个类模板—优先队列(stl):

STL中定义优先队列的模板类为priority_queue，其定义如下：
templateclass priority_queue;
模板里面有三个参数，第一个为元素的类型，第二个为所使用的容器（vector或deque），第三个为一个比较的规则，决定是大优先队列还是最小优先队列，默认的less为大优先队列，实现方式是大堆，greater为最小优先队列，实现方式是最小堆，结构都是二叉树。

大根堆就是根节点大，小根堆就是根节点最小。

#include//c++标准头文件，可以使用cout,cin等标准库函数 
#include//使用priority_queue时需要的头文件 
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
struct test {//定义一个结构体test 
	int val;
	test(int v) {//构造函数 
		this->val = v;
	}
	bool operator >(const test t)const {//重载运算符>if (val >t.val)
			return true;
		else
			return false;
	}
	bool operator< (const test t)const {//重载运算符
		return val< t.val;
	}
};
int main() {priority_queue, less>q1;//定义一个大顶堆q1 
	cout<< "定义一个大根堆q1: priority_queue,less>q1"<< endl;
	q1.push(test(10));//向队列中添加一个test，val的值为10 
	q1.push(test(5));//向队列中添加一个test，val的值为5
	q1.push(test(7));//向队列中添加一个test，val的值为7
	cout<< "按顺序添加val的值为10、5、7的test,目前队列的元素：test(10) test(5) test(7)"<< endl;
	cout<< "q1.top().val="<< q1.top().val<< endl;
	cout<< endl;


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


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

	q1.pop();
	cout<< "q1.pop()后，目前队列是空的"<< endl;
	cout<< "目前队列是空的，不能使用q1.top()查询队首元素"<< endl;
	cout<< endl<< endl;



	priority_queue, greater>q2;//定义一个大顶堆q1 
	cout<< "定义一个小根堆q2: priority_queue,greate>q2"<< endl;
	q2.push(test(10));//向队列中添加一个test，val的值为10 
	q2.push(test(5));//向队列中添加一个test，val的值为5
	q2.push(test(7));//向队列中添加一个test，val的值为7
	cout<< "按顺序添加val的值为10、5、7的test,目前队列的元素：test(10) test(5) test(7)"<< endl;
	cout<< "q2.top().val="<< q2.top().val<< endl;
	cout<< endl;


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


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

	q2.pop();
	cout<< "q1.pop()后，目前队列是空的"<< endl;
	cout<< "目前队列是空的，不能使用q2.top()查询队首元素"<< endl;


}

题目：dijkstra优化

#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;
}