调用优先队列时可以利用相反数将大根堆变成小根堆
小根堆:
priority_queue<pair<int,int>> heap
;插入元素:
heap.push(-d[y],y)
;
题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值
请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1
样例
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
分析
(朴素版dijkstra) $O(n^2)$
因为$O(n^2)$在 Dijkstra求最短路 II 中会严重超时,所以不可行
上一题代码中主要瓶颈在于全局找最小值的过程
可以利用二叉堆对d数组进行维护,用$O(logn)$的时间获得最小值并删除
最终用$O(mlogn)$实现了dijkstra
算法
(二叉堆版dijkstra) $O(mlogn)$
$\color{#32CD32}{Accepted}$ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=150010;
int n,m;
int e[N],w[N],ne[N],h[N],idx;
int d[N],st[N];
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
memset(d,0x3f,sizeof d);
priority_queue<PII,vector<PII>,greater<PII>> heap;
//因为是优先队列,所以要把距离放在first
d[1]=0;
heap.push({0,1});
while(heap.size())
{
PII tot=heap.top();
heap.pop();
int pos=tot.second;//记录位置
int dis=tot.first;//记录距离
if(st[pos])continue;
st[pos]=1;
//更新所有相连的点
for(int i=h[pos];~i;i=ne[i])
{
int j=e[i],k=w[i];//编号和距离
if(d[j]>d[pos]+k)
{
//更新,入队
d[j]=d[pos]+k;
heap.push({d[j],j});
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
//单源最短路径
dijkstra();
if(d[n]==0x3f3f3f3f)printf("-1");
else printf("%d",d[n]);
return 0;
}