AcWing 850. Dijkstra求最短路 II
原题链接
简单
作者:
chI_mo
,
2023-07-07 22:02:23
,
所有人可见
,
阅读 109
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5+10;
//稀疏图用邻接表,并且这么大的N如果直接开数组,二维数组会报错
int h[N], e[2*N], ne[2*N], w[2*N];//多一个权值
int idx;
int dis[N];//起点到某点的距离
priority_queue<pii,vector<pii>,greater<pii>> heap;//小顶堆 队头是距离最小的元素
int st[N];//如果有重边,在添加过程中就会出现重复的边在堆内,但由于会优先取最小距离的边,所以冗余边没关系
int n,m;
void add(int a,int b, int c){//添加a到b的边 权值为c
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dijkstra(int u){
memset(dis,0x3f,sizeof dis);
dis[u] = 0;
heap.push({0,1});
while(!heap.empty()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;//距离
if(st[ver]) continue;//冗余边,已经访问过,可以跳过,因为每次优先取更小的边,访问到已访问过的说明这次的距离更大
st[ver] = 1;//标记访问过的边
/**
*把Extract-Min操作和Relax操作一起完成了
*/
for(int i = h[ver];i != -1;i = ne[i]){
int j = e[i];//取编号
/**
*distance为起点到ver的距离 , w[i]为ver到e[i]的的距离
*如果 起点直接到j距离 比 起点到ver再到e[i] 更远,那么就更新dis[j]
*/
dis[j] = min(dis[j],distance + w[i]);
heap.push({dis[j],j});//可以直接添加,冗余的会跳过
}
}
if(dis[n] == 0x3f3f3f3f) return -1;
return dis[n];
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
int x,y,z;
while(m--){
cin>>x>>y>>z;
add(x,y,z);
}
cout<<dijkstra(1);
return 0;
}