堆优化版dijistra $O(nlogm)$ ,注意typedef pair<int,PII>PIII
中的int
和PII
不能写反
因为我们是对距离更新,又因为priority_queue排序是按begin位置排序
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
typedef pair<int,PII>PIII;
const int N = 1e5+10,M = 2*N;
int e[M],ne[M],h[N],w[M],idx;
int dist[N][2];//0表示最短路,1表示次短路
bool st[N][2];
int n,m;
priority_queue<PIII,vector<PIII>,greater<PIII>>q;
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijistra(){
memset(dist,0x3f,sizeof dist);
dist[1][0]=0;
q.push({dist[1][0],{1,0}});
while(q.size()){
PIII t=q.top();
q.pop();
int ver=t.second.first,d=t.first,type=t.second.second;
if(st[ver][type])continue;
st[ver][type]=true;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(dist[j][0]>d+w[i]){
dist[j][1]=dist[j][0];
q.push({dist[j][1],{j,1}});
dist[j][0]=d+w[i];
q.push({dist[j][0],{j,0}});
}else if(dist[j][1]>d+w[i]&&dist[j][0]<d+w[i]){
dist[j][1]=d+w[i];
q.push({dist[j][1],{j,1}});
}
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dijistra();
cout<<dist[n][1];
return 0;
}
请问一下,为什么要把次短路也要加入到队列中呢?我没有想明白
这个就是关于严格次短路和非严格次短路的问题,对于这个问题的讲解,算法提高课有详细讲解,你可以看看别人的解题(我感觉我讲的不怎么行)