堆优化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;
}