优先队列怎么用
查看原帖
优先队列怎么用
571132
Soft_cute楼主2023/8/10 18:38

想要dijkstra+vector存边+堆优化代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1e4+10,M=1e5+10;
int n,m,s,a[N][N];
struct Node{
	vector<int> childs;
	int dis;
	int deep;
	int size;
	bool f=false;
}g[N];
struct cmp{
	bool operator() (const Node &a,const Node &b){
		return a.dis>b.dis;
	}
};
void add(int x,int y,int z){
	g[x].childs.push_back(y);
	g[y].childs.push_back(x);
	g[x].size=x,g[y].size=y;
	a[x][y]=a[y][x]=z;
}
void dijkstra(){
	for(int i=1;i<=n;i++) g[i].dis=inf;
	priority_queue<Node,vector<Node>,cmp> heap;
	heap.push(g[1]);
	while(heap.size()){
		Node t=heap.top;
		heap.pop();
		int ver=t.size,distance=t.dis;
		if(g[ver].f) continue;
		g[ver].f=true;
		for(int i=0;i<g[ver].childs.size();i++){
			int j=g[ver].childs[i];
			if(g[j].dis>distance+a[i][j]){
				g[j].dis=distance+a[i][j];
				heap.push(g[j]);
			}
		}
	}
	if(g[n].dis==inf) return -1;
	return g[n].dis;
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,c;
		cin>>x>>y>>c;
		add(x,y,c);
	}
	cout<<dijkstra();
} 

我写的不怎么对,不知道优先队列怎么用

2023/8/10 18:38
加载中...