1 条题解
-
2XzyStudio (admin) LV 8 MOD RP++ 机房蒟蒻 tayz @ 2023-10-21 09:38:15
本题解同时包含Dijkstra和SPFA、Dijkstra堆优化三种做法
Dijkstra朴素版时间复杂度\(O(n^2)\),适合稠密图。使用优先队列/堆优化后为\(O(mlogn)\)
SPFA时间复杂度平均\(O(m)\),最坏\(O(nm)\),图中含负权边,且没有经过的边数\(l \leqslant k\)的都考虑使用SPFA。本质上是对Bellman-Ford的优化。
#include<bits/stdc++.h> #define INF 2147483647 #define MAXN 500005 using namespace std; int n, m, s, cnt; int dis[MAXN], h[MAXN], to[MAXN], val[MAXN], nxt[MAXN]; bool vis[MAXN]; void add(int u, int v, int w){ // 链式前向星存图 to[++cnt] = v; val[cnt] = w; nxt[cnt] = h[u]; h[u] = cnt; } void Dijkstra(int s){ for(int i=0; i<=n; i++) dis[i] = INF; // 初始化为无穷大 dis[s] = 0; while(true){ int u=0; for(int i=1; i<=n; i++){ if(!vis[i] && dis[i]<dis[u]) u=i; // 寻找未被标记的最小的点 } if ( u == 0 ) break; // 没有可处理的点,退出 vis[u] = true; // 标记该点 for(int i=h[u]; i; i=nxt[i]){ int v=to[i]; dis[v] = min(dis[v], dis[u]+val[i]); // 更新最短路 } } } queue<int> q; void SPFA(int s){ for(int i=0; i<=n; i++) dis[i] = INF; // 初始化为无穷大 dis[s] = 0; vis[s] = true; // 标记该点 q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=h[u]; i; i=nxt[i]){ int v=to[i]; if(dis[v]>dis[u]+val[i]){ // 如果可以松弛 dis[v]=dis[u]+val[i]; q.push(v); // 松弛后入队 } } } } int main(){ cin>>n>>m>>s; for(int i=1, u, v, w; i<=m; i++){ cin>>u>>v>>w; add(u, v, w); } Dijkstra(s); SPFA(s); // 选取一个进行调用! for(int i=1; i<=n; i++) cout<<dis[i]<<" "; return 0; }
堆优化:(可以过Luogu P4779 标准版)
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e5+10; const int maxm = 2e5+10; const int INF = (1<<31)-1; int head[maxm], vis[maxn]; LL dix[maxn]; int n, m, s, tot=0; struct node{ int to, nxt, d; }edge[maxm]; struct Point { // 自定义一个小根堆 int dd, p; // dd表示 p点到起点的距离 bool operator <(const Point &x) const { return dd > x.dd; } }; void add(int x, int y, int z){ edge[tot].to = y; edge[tot].d = z; edge[tot].nxt = head[x]; head[x] = tot++; } void dijkstra(){ for(int i=1; i<=n; ++i) dix[i] = INF; memset(vis, 0 ,sizeof(vis)); dix[s] = 0; priority_queue<Point> que; Point a; a.dd = 0; a.p = s; // 起点 que.push(a); // 把起点放入小根堆中 while(que.size()){ //取出堆顶元素,也就是全局最小的 dix a = que.top(); que.pop(); int x = a.p; if(vis[x]) continue; vis[x] = 1; //扫描 x 所有的出边 for(int i=head[x]; i!=-1; i=edge[i].nxt){ int y = edge[i].to; if(dix[y] > dix[x] + 1LL*edge[i].d) { // 当对点 y 可以被更新的时候 dix[y] = dix[x] + 1LL * edge[i].d; a.dd = dix[y]; a.p = y; que.push(a); } } } } int main(){ scanf("%d%d%d", &n, &m, &s); memset(head, -1, sizeof(head)); while(m--){ int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); } dijkstra(); for(int i=1; i<n; ++i) printf("%lld ", dix[i]); printf("%lld\n", dix[n]); return 0; }
- 1