拯救蒟蒻大作战
查看原帖
拯救蒟蒻大作战
1530321
Wzmois楼主2025/2/5 15:06

堆优化Dijkstra哪里有问题。。。救救我。。。。

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=1e6,INF=0x3f3f3f3f;
int n,m,hd[N],val[N],w[N],nex[N],idx=1,d[N];
bool vis[N];
void add(int a,int b,int c){
	val[idx]=b,w[idx]=c,nex[idx]=hd[a],hd[a]=idx++;
}
int Heap_Dijkstra(int st,int en){
	memset(d,INF,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[st]=0;
	priority_queue<pii,vector<pii>,greater<pii> > h;
	h.push({0,st});
	while(h.size()){
		auto t=h.top();
		h.pop();
		int pos=t.second,dist=t.first;
		if(vis[pos]) continue;
		vis[pos]=1;
		for(int i=hd[pos];i!=-1;i=nex[i]){
			int j=val[i];
			if(d[j]>d[pos]+w[i]){
				d[j]=d[pos]+w[i];
				h.push({d[j],j});
			}
		}
	}
	if(d[en]==INF) return -1;
	return d[en];
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	memset(hd,-1,sizeof(hd));
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	cout<<Heap_Dijkstra(1,n);
	return 0;
}


2025/2/5 15:06
加载中...