AcWing 850. Dijkstra求最短路 II
原题链接
简单
作者:
y_96
,
2024-04-04 19:02:30
,
所有人可见
,
阅读 1
#include<iostream>
#include<queue>
#include<unordered_map>
#include<forward_list>
#include<unordered_set>
#include<cstring>
using namespace std;
const int N=100010;
typedef pair<int,int>PII;
forward_list<PII>h[N];//稀疏图用邻接表(点多边少)注意看n和m的数据范围
int n,m;
int dijkstra(){
unordered_set<int>s;
unordered_map<int,int>dist;
dist[1]=0;
for(int i=2;i<=n;i++)
dist[i]=0x3f3f3f3f;//正无穷 确保数据范围内加法不会溢出为负数
priority_queue<PII,vector<PII>,greater<PII>>heap;//pair优先以first比较大小
heap.push({0,1});
while(heap.size()){
PII cur=heap.top();
heap.pop();
int t=cur.second;
if(s.count(t))//扔掉冗余元素
continue;
s.insert(t);
for(auto& e:h[t]){//邻接表只会遍历到能去的点
int j=e.second,dtj=e.first;
dist[j]=min(dist[j],dist[t]+dtj);
heap.push({dist[j],j});//用数据冗余代替修改元素 O(n*logm)
}
}
return dist[n]==0x3f3f3f3f?-1:dist[n];
}
int main(){
cin>>n>>m;
while(m--){
int a,b,x;
cin>>a>>b>>x;
h[a].push_front({x,b});
}
cout<<dijkstra();
return 0;
}