图论
本文将介绍Dijkstra、Bellman-Ford、SPFA、Floyd等算法
注意：本文图文并茂
将提供以下图文链接供大家理解：
图文链接：
飞书图解链接🎉🎉🎉
密码：L1@75666
1. Dijkstra算法题目1
Acwing 849. Dijkstra求最短路 I
#includeusing namespace std;const int N = 5e2 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;int g[N][N], dist[N];bool st[N];int n, m;int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for(int i = 1; i < n; i ++ ){ int t = 0; for(int j = 1; j dist[j]) t = j; } for(int j = 1; j dist[t] + g[t][j]){ dist[j] = dist[t] + g[t][j]; } } st[t] = true; } if(dist[n] == INF) return -1; else return dist[n];}int main(){ memset(g, 0x3f, sizeof g); scanf("%d%d", &n, &m); int a, b, c; while(m -- ){ scanf("%d%d%d", &a, &b, &c); g[a][b] = min(g[a][b], c); } printf("%d\n", dijkstra()); for(int i = 0; i <= n; i ++ ){ printf("%s ", st[i] ? "true" : "false"); } puts(""); return 0;}题目2
Luogu P3371 【模板】单源最短路径（弱化版）
#includeusing namespace std;const int N = 1e4 + 10, M = 5e5 + 10, INF = INT_MAX;struct edge{ int v, w;};int dist[N];bool st[N];vector e[N];int n, m, s;void dijkstra(int a){ for(int i = 0; i <= n; i ++ ) dist[i] = INF; dist[a] = 0; for(int i = 1; i < n; i ++ ){ int t = 0; for(int j = 1; j dist[j]) t = j; } st[t] = true; for(auto &edge: e[t]){ int v = edge.v, w = edge.w; if(dist[v] > dist[t] + w) dist[v] = dist[t] + w; } }}int main(){ scanf("%d%d%d", &n, &m, &s); int a, b, c; while(m -- ){ scanf("%d%d%d", &a, &b, &c); e[a].push_back({b, c}); } dijkstra(s); for(int i = 1; i <= n; i ++ ){ printf("%d ", dist[i]); } return 0;}题目3
P4779 【模板】单源最短路径（标准版）
#includeusing namespace std;typedef pair PII;const int N = 1e5 + 10, M = 2e5 + 10, INF = INT_MAX;struct edge{ int v, w;};int dist[N];bool st[N];int n, m, s;vector e[N];priority_queue<PII, vector, greater> q;void dijkstra(int s){ for(int i = 0; i dist[u] + w){ dist[v] = dist[u] + w; q.push({dist[v], v}); } } }}int main(){ scanf("%d%d%d", &n, &m, &s); int a, b, c; while(m -- ){ scanf("%d%d%d", &a, &b, &c); e[a].push_back({b, c}); } dijkstra(s); for(int i = 1; i <= n; i ++ ){ printf("%d ", dist[i]); } return 0;}题目4
AtCoder E – Skiing
题意如下：
E – 滑雪
AtCoder 滑雪场有\(N\)个开放区，分别是Space 1， Space 2，…，Space N. Space \(i\) 的海拔是\(H_i\)，有\(M\)个斜坡双向连接两个Space. 第\(i(1 \leq i \leq M)\)个斜坡连接Space \(U_i\)和\(V_i\). 在任意两个空间之间使用一些斜坡是可能的。Takahashi仅通过斜坡从一个Space通过另一个Space. 每次通过一个斜坡他的幸福感改变. 具体地说，当他使用斜坡从Space \(X\) 到 Space \(Y\)，他的幸福感变化如下:
- 如果Space \(X\)的海拔严格高于 Space \(Y\)，他的幸福感增加\(H_X – H_Y\).
- 如果Space \(X\)的海拔严格低于 Space \(Y\)，他的幸福感下降\(2 \times (H_Y – H_X)\).
- 如果Space \(X\)的海拔等于 Space \(Y\)，他的幸福感不变.
幸福感可能是负值.
起初，Takahashi在Space 1,并且他的幸福感是0，找到他在通过任意数量（可能是0）的斜坡之后最大可能的幸福感，停止在任何Space.
数据范围：
- \(2 \leq N \leq 2 \times 10^5\)
- \(N – 1 \leq M \leq min(2 \times 10^5, \frac {N(N – 1)}{2})\)
- \(0 \leq H_i \leq 10^8 (1 \leq i \leq N)\)
- \(1 \leq U_i < V_i \leq N (1 \leq i \leq M)\)
- \((U_i,V_i) \neq (U_j,V_j) \quad if \quad i \neq j\)
- 输入的所有值是整数
- 在任意两个Space之间使用一些斜坡是可能的(重边)。
输入：
N MH1 H2 ... HNU1 V1U2 V2...UM VM输出：
打印答案。
样例输入1:
4 410 8 12 51 21 32 33 4样例输出1：
3样例解释：
如果 Takahashi 从 Space 1 -> Space 3 -> Space 4,他的幸福感变化如下：
- 当他从Space1(海拔10)到Space3(海拔12)，他的幸福感下降\(2 \times (12 – 10) = 4\)，幸福感变为\(-4\).
- 当他从Space3(海拔12)到Space4(海拔5)他的幸福感上升\(12 – 5 = 7\),并且变为了(-4 + 7 = 3)
如果他结束滑雪，最终的幸福感是3，这是最大可能的值。
样例输入2:
2 10 101 2样例输出2：
0他一点不移动的幸福感最大。
题解如下AC代码如下：
#includeusing namespace std;typedef long long LL;typedef pair PII;const int N = 2e5 + 10, INF = INT_MAX;struct edge{ int v, w;};LL dist[N];int h[N];bool st[N];int n, m;vector e[N];priority_queue<PII, vector, greater> q;void dijkstra(int s){ for(int i = 0; i dist[u] + w){ dist[v] = dist[u] + w; q.push({dist[v], v}); } } }}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i h[v]){ // h[u] > h[v] e[u].push_back({v, 0}); e[v].push_back({u, h[u] - h[v]}); }else{ // h[v] > h[u] e[v].push_back({u, 0}); e[u].push_back({v, h[v] - h[u]}); } } dijkstra(1); LL ans = 0; for(int i = 1; i <= n; i ++ ){ if(dist[i] == INF) continue; ans = max(ans, -(dist[i] - h[1] + h[i])); } printf("%lld\n", ans); return 0;}2. Bellman-Ford算法题目1
Luogu P3385 【模板】负环
#includeusing namespace std;const int N = 2e3 + 10, INF = 0x3f3f3f3f;struct edge{ int v, w;};vector<vector> e(N);int dist[N], cnt[N]; // cnt 表示点i距离远点的边数bool st[N];queue q;int T, n, m;bool bellman_ford(int s){ memset(dist, 0x3f, sizeof dist); dist[s] = 0; bool flag; // 是否松弛 for(int i = 1; i <= n; i ++ ){ flag = false; for(int u = 1; u dist[u] + w){ dist[v] = dist[u] + w; flag = true; } } } if(!flag) break; } return flag;}int main(){ scanf("%d", &T); int a, b, c; while(T -- ){ e.clear(); e.resize(N); scanf("%d%d", &n, &m); while(m -- ){ scanf("%d%d%d", &a, &b, &c); if(c >= 0) e[b].push_back({a, c}); e[a].push_back({b, c}); } printf("%s\n", bellman_ford(1) ? "YES" : "NO"); } return 0;}3. SPFA算法题目1
Luogu P3385 【模板】负环
#includeusing namespace std;const int N = 2e3 + 10, INF = 0x3f3f3f3f;struct edge{ int v, w;};vector<vector> e;int dist[N], cnt[N];bool st[N];queue q;int T, n, m;bool spfa(int s){ memset(dist, 0x3f, sizeof dist); dist[s] = 0; st[s] = true; q.push(s); while(q.size()){ int u = q.front(); q.pop(); st[u] = false; for(auto const &edge : e[u]){ int v = edge.v, w = edge.w; if(dist[v] > dist[u] + w){ dist[v] = dist[u] + w; cnt[v] = cnt[u] + 1; if(cnt[v] >= n) return true; if(!st[v]) q.push(v), st[v] = true; } } } return false;}int main(){ scanf("%d", &T); while(T -- ){ e.clear(); e.resize(N); // 清空 q while(!q.empty()) q.pop(); memset(cnt, 0, sizeof cnt); memset(st, 0, sizeof st); scanf("%d%d", &n, &m); int a, b, c; while(m -- ){ scanf("%d%d%d", &a, &b, &c); if(c >= 0) e[b].push_back({a, c}); e[a].push_back({b, c}); } printf("%s\n", spfa(1) ? "YES" : "NO"); } return 0;}题目2
TODO
4. Floyd算法题目1
AcWing 854. Floyd求最短路
#includeusing namespace std;const int N = 2e2 + 10, INF = 0x3f3f3f3f;int g[N][N];int n, m, q;void floyd(){ for(int k = 1; k <= n; k ++ ) for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}int main(){ scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n; i ++ ){ for(int j = 1; j INF / 2) puts("impossible"); else printf("%d\n", g[a][b]); } return 0;}