题目分析
其实该算法与朴素Dijkstra算法的思想是一致的
即每次都从未被访问过的点中选择到目标点最近的那一个,并使用该点更新其他点到目标点的距离
只不过该算法借用了优先权队列的自动有序特点,避免了排序
核心点
该算法的优先权队列中可能会存在着从某一个点到目标点的多组路径值,我们选择最小的那一个也就是排在最前面的那一个即可,后面的直接跳过
if(vis[poi]==1) continue; //当存在某一个点到目标点的多组路径值时,选最前面也就是最小的那一个,其余的跳过
vis[poi]=1;
算法
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=160000;
const int INF=10000000;
int vis[N];
int dis[N];
vector<PII> adj[N];
int n,m;
void Dijkstra(){
fill(dis,dis+N,INF);
dis[1]=0;
priority_queue<PII,vector<PII>,greater<PII> >heap;
heap.push({0,1}); //first存储距离 second存储编号
while(!heap.empty()){
PII temp=heap.top();
heap.pop();
int val=temp.first;
int poi=temp.second;
//当存在某一个点到目标点的多组路径值时,选最前面也就是最小的那一个,其余的跳过
if(vis[poi]==1) continue;
vis[poi]=1;
int len=adj[poi].size();
for(int i=0;i<len;i++){ //更新与该点相连的点到目标点的距离
int v=adj[poi][i].first;
int p=adj[poi][i].second;
if(val+v<dis[p]&&vis[p]==0){
dis[p]=val+v;
heap.push({dis[p],p});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
adj[x].push_back({z,y});
}
Dijkstra();
if(dis[n]!=INF)cout<<dis[n]<<endl;
else cout<<"-1";
return 0;
}