dijkstra解法
1.距离要初始化为inf
2.边的存储要弄清存储的方式,以及各自代表的含义;
比如说pair存储,first代表边的指向的点,second代表边的权值,而数组的第一维代表边的起点。
3.优先队列存储的信息要清楚它的作用:
存储距离:目的是对距离进行排序,每次取出距离最小的节点,功能只是对队列的节点进行排序。
存储节点:目的是为了取出最短距离的节点时,能够获得节点的编号。
所以在优先队列里面,存储距离加了个负号,因为优先队列优先对pair的第一个元素进行降序排序,所以为了取出最小距离的节点,需要加个负号。
并且加了负号的距离并没有对我们产生影响,我们需要的只是节点的编号。
#include<bits/stdc++.h> using namespace std; #define se second #define fi first typedef pair<int,int> pii; typedef long long ll; const int N = 2e5+5; const int inf = 0x3f3f3f3f; vector<pii>e[N]; ll dis[N]; void dijkstra() { int x = 1; priority_queue<pii>q; dis[x] = 0; q.push({-dis[x],x}); while(!q.empty()) { pii t = q.top(); q.pop(); for(int i=0;i<e[t.se].size();i++) { int too = e[t.se][i].fi; if(dis[too] > dis[t.se] + e[t.se][i].se) { dis[too] = dis[t.se] + e[t.se][i].se; q.push({-dis[too],too}); } } } } int main() { for(int i=1;i<=N;i++) dis[i] = inf; int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; e[a].push_back({b,c}); e[b].push_back({a,c}); } dijkstra(); if(dis[n]!=inf) cout<<dis[n]<<'\n'; else cout<<"qwb baka\n"; return 0; }
SPFA做法
#include<bits/stdc++.h> using namespace std; #define se second #define fi first typedef pair<int,int> pii; typedef long long ll; const int N = 2e5+5; const int inf = 0x3f3f3f3f; vector<pii>e[N]; ll dis[N]; bool vis[N]; void spfa() { int s = 1; vis[s] = 1; dis[s] = 0; queue<int>q; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i=0;i<e[u].size();i++) { int v = e[u][i].fi; if(dis[v] > dis[u]+e[u][i].se) { dis[v] = dis[u] + e[u][i].se; if(!vis[v]) { vis[v] = true; q.push(v); } } } } } int main() { for(int i=1;i<=N;i++) dis[i] = inf; int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; e[a].push_back({b,c}); e[b].push_back({a,c}); } spfa(); if(dis[n]!=inf) cout<<dis[n]<<'\n'; else cout<<"qwb baka\n"; return 0; }
————————————————
版权声明:本文为CSDN博主「行码棋」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。欢迎大家交流。
原文链接:https://blog.csdn.net/qq_50285142/article/details/116573053