蓝桥杯模板总结：_C

堆优化的DIJ单源最短路：

#include
#include
#include
#include
using namespace std;
int read(){
	int x,f;
	x=0;f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,m,s;
struct bnode{
	int cd;
	int v;
};
vector dt[100009];
int bj[100009]={0};
int dis[100009]={0};
struct node{
	int xh;
	int dx;
};
struct cmp{
	
	bool operator() (node a,node b){
	return a.dx>b.dx;
	}
};
priority_queue,cmp> pp;

int main(){
	n=read();m=read();s=read();
	int ma,mb,mv;
	for(int i=1;i<=m;i++){
		ma=read();mb=read();mv=read();
		bnode tmp;
		tmp.cd=mb;tmp.v=mv;
		dt[ma].push_back(tmp);
	}
	for(int i=0;idis[tmp.xh]+dt[tmp.xh][i].v){
	//			cout<

 
两个坑点： 
①优先队列的结构体重定义排序，排序函数的规则和sort的规则相反，需要变一下。

 
②大数据量加快读 
 
堆优化的SPFA单源最短路： 
#include
#include
#include
#include
using namespace std;
int read(){
	int x,f;
	x=0;f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,m,s;
struct bnode{
	int cd;
	int v;
};
vector dt[100009];
int bj[100009]={0};
int dis[100009]={0};
struct node{
	int xh;
	int dx;
};
struct cmp{
	
	bool operator() (node a,node b){
	return a.dx>b.dx;
	}
};
priority_queue,cmp> pp;

int main(){
	n=read();m=read();s=read();
	int ma,mb,mv;
	for(int i=1;i<=m;i++){
		ma=read();mb=read();mv=read();
		bnode tmp;
		tmp.cd=mb;tmp.v=mv;
		dt[ma].push_back(tmp);
	}
	for(int i=0;idis[tmp.xh]+dt[tmp.xh][i].v){
	//			cout<
 
注意: 
①堆优化的spfa和dij很相似，代码重合度为98%，只是dij出队后不会再次入队，但是spfa出队后会再次入队。

 
②spfa可以用来求单源最长路，但是dij不可以。

 
 
单源最短路模板DIJ： 
#include
#include
#include
using namespace std;
int n,m,s;
int read(){
	int x,f;
	x=0;f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int bj[10009]={0};
int dis[10009]={0};
struct bian{
	int cd;
	int val;
};
vector dt[10009];
int getwz(){
	int minn=0x7fffffff;
	int minwz;
	for(int i=1;i<=n;i++){
		if(bj[i]==0&&dis[i]dis[wz]+dt[wz][j].val){
				dis[dt[wz][j].cd]=dis[wz]+dt[wz][j].val;
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		cout<
 
FLOYD：多元最短路 
#include
#include
#include
using namespace std;
int n,m;
int read(){
	int x,f;
	x=0;f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int dp[1009][1009]={0};
int main(){
	n=read();
	m=read();
	int ma,mb,mc;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=100009;
		}
		dp[i][i]=0;
	}
	for(int i=1;i<=m;i++){
		ma=read();mb=read();mc=read();
		if(dp[ma][mb]>mc)
		dp[ma][mb]=mc;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dp[i][j]>dp[i][k]+dp[k][j])
					dp[i][j]=dp[i][k]+dp[k][j];
			}
		}
	}
	return 0;
} 
坑点： 
①dp数组的初始值一定要赋值成比最长边还要大的数字，但是如果赋值成0x7fffffff，会导致任意两个不存在的边相加后溢出int范围变成负数，得到负边，所以初始值尽量保证两个初始值相加不超过int 
②没边的赋值成最大值，有边的赋值成边权值即可。

 
 
最短路题型：如果要求所有点到任意一点的最短路，可以反向建图，再从单点跑一遍最短路即可。

 
 
堆排序： 
#include
#include
using namespace std;
int n;
int sz[1009]={0};
void jh(int wz){
	if(wz>n/2)return;
	int jl;
	if(sz[2*wz]>sz[2*wz+1])jl=2*wz;
	else jl=2*wz+1;
	if(sz[wz]>n;
	for(int i=1;i<=n;i++){
		cin>>sz[i];
	}
	for(int i=n/2;i>=1;i--){
		jh(i);
	}
	for(int i=1;i<=n;i++){
		cout<
 
堆排序：核心代码是jh函数，交换函数，将堆中以wz为根的堆重新构造堆；					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/564007.html

蓝桥杯模板总结：

发表评论

评论列表（0条）