几点注意:
1 关于为什么不能把
heap.push({0,1})
改成heap.push({1,0})
然后改变下面int ver = t.first, distance = t.second;
的原因是:
greater[HTML_REMOVED]
意味着队列将按照pair 的第一个元素
(即first
)进行降序排序。如果两个pair
的first
相同,那么它们将按照second
进行升序排序。
那么在本题中如果将heap.push({0, 1})
改为heap.push({1, 0})
并相应地更改int ver = t.first, distance = t.second;
为int ver = t.second, distance = t.first;
,那么问题就会出现。在这种情况下,您实际上是在将顶点编号作为first
,而将距离作为second
。但是,由于greater[HTML_REMOVED]
的排序规则,队列将按照顶点编号(second)进行降序排序,而不是按照距离(first)进行排序。
2 在这段 Dijkstra 算法的实现中,
dist[ver]
和distance
等价,因为在算法的每一步中,它们表示的都是从起点到当前顶点 ver 的最短距离
3 是w[i] 而不是w[j]的原因:
在 Dijkstra 算法中,边权重 w[i] 而不是 w[j]被用于计算从起点到顶点 j 的距离
,是因为 i 是当前顶点 ver 的出边索引
,而 j 是该出边指向的邻接顶点
。
具体来说,当算法处理顶点 ver 时,它会遍历从 ver 出发的所有边。对于每条边,算法会检查通过这条边从 ver 到邻接顶点 j 是否可以得到更短的路径。这里,i 是当前正在考虑的从 ver 出发的边的索引
,而j 是这条边指向的顶点
。
边权重数组 w 存储了图中每条边的权重。在 add 函数中,当你添加一条从 a 到 b 的边,并赋予它权重 c 时,这个权重 c 会被存储在 w[idx] 中,其中idx 是当前边的索引
。因此,当你想要获取从 ver 通过边 i 到顶点 j 的距离时,你应该使用 w[i],因为i 是指向这条边的索引,而这条边连接了 ver 和 j。
简单来说,w[i] 是边 (ver, j) 的权重
,其中 i 是这条边的索引,而 j 是这条边指向的顶点。因此,在计算 dist[j](从起点到顶点 j 的最短距离)时,你会使用 dist[ver] + w[i],这里 dist[ver] 是从起点到当前顶点 ver 的已知最短距离,而 w[i] 是从 ver 到 j 的边的权重。
堆优化:可直接求出最小值O(1)
用优先队列(堆)
模板不变 并套用BFS
Dijkstra模板:
BFS在图表中的模板:
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
int n,m;
int head[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];//优先队列没有插入操作 会产生冗余 最小值之前可能已经处理过 所以用st[]数组判断一下
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=head[a];
w[idx]=c;
head[a]=idx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof(dist));
dist[1]=0;//初始化
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second,distant=t.first;
if(st[ver]==true) continue;
st[ver]=true;//冗余备份
for(int i=head[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>distant+w[i]){
dist[j]=distant+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;//如果第n个点 没有被更新到 说明和源点不连通
return dist[n];
}
int main(){
memset(head,-1,sizeof head);
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);//邻接表不用处理重复边的问题
}
cout<<dijkstra()<<endl;
return 0;
}