Loading... # 单源最短路 ## dijkstra 稠密图 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 1e4; int n, m, s; int g[N][N]; int dist[N]; bool st[N]; void dijkstra() { memset(dist, 0x3f, sizeof dist); dist[s] = 0; for (int i = 0; i < n; i++) { int t = -1; for (int j = 1; j <= n; j++) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for (int j = 1; j <= n; j++) { dist[j] = min(dist[j], dist[t] + g[t][j]); } } // if(dist[n] == 0x3f3f3f3f) return -1; // else return n; } int main() { scanf("%d %d %d", &n, &m, &s); memset(g, 0x3f, sizeof g); int a, b, c; while (m--) { scanf("%d %d %d", &a, &b, &c); g[a][b] = min(g[a][b], c); } // int t = dijkstra(); // printf("%d", t); dijkstra(); for (int i = 1; i <= n; i++) printf("%d ", dist[i]); return 0; } ``` ## 堆优化dijkstra ```cpp #include<bits/stdc++.h> using namespace std; const int N = 2e6 + 5; typedef pair<int, int> PII; int n, m, s; int h[N], ne[N], e[N], w[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dijkstra() { memset(dist, 127, sizeof dist); dist[s] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, s}); while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } // if(dist[n] == 0x3f3f3f3f) return -1; // else return n; } int main() { scanf("%d %d %d", &n, &m, &s); memset(h, -1, sizeof h); int a, b, c; while (m--) { scanf("%d %d %d", &a, &b, &c); add(a, b, c); } // int t = dijkstra(); // printf("%d", t); dijkstra(); for (int i = 1; i <= n; i++) printf("%d ", dist[i]); return 0; } ``` ## Bellman-Ford ```cpp #include <bits/stdc++.h> using namespace std; const int N = 505, M = 10010; int n, m, k; int dist[N], backup[N], st[N]; struct Node { int a, b, w; } edges[M]; int b_f() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < k; i++) { memcpy(backup, dist, sizeof dist); for (int j = 0; j < m; j++) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; dist[b] = min(dist[b], backup[a] + w); } } if (dist[n] >= 0x3f3f3f3f / 2) return -1; else return dist[n]; } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); edges[i] = {x, y, z}; } int t = b_f(); if (t == -1 && dist[n] != -1) printf("impossible"); else printf("%d", t); return 0; } ``` ```java // 滚动数组 while (k-- >= 0) { var cur = Arrays.copyOf(dist, dist.length); for (int[] e: flights) { cur[e[1]] = Math.min(cur[e[1]], dist[e[0]] + e[2]); } dist = cur; } ``` ## SPFA  #### 输入样例 ``` 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 ``` #### 输出样例 ``` 8 ``` #### AC ```cpp #include<bits/stdc++.h> using namespace std; const int N = 510, P = 805, C = 1455 * 2; // 无向图 边 * 2; bool st[P]; int cow[N]; int dist[P]; int ne[C], e[C], h[C], w[C], idx; void add(int a, int b, int v) { e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx++; } void spfa(int cw) { memset(dist, 0x3f, sizeof dist); dist[cw] = 0; queue<int> q; q.push(cw); st[cw] = true; while (!q.empty()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } } } } int main() { int n, p, c; cin >> n >> p >> c; for (int i = 0; i < n; i++) cin >> cow[i]; memset(h, -1, sizeof h); for (int i = 0; i < c; i++) { int a, b, v; cin >> a >> b >> v; add(a, b, v); add(b, a, v); } int res = 0x3f3f3f3f, t = 0; for (int i = 1; i <= p; i++) { t = 0; spfa(i); for (int j = 0; j < n; j++) { if (t >= 0x3f3f3f3f) continue; t += dist[cow[j]]; } res = min(res, t); } cout << res; return 0; } ``` ## 负环判断 ```cpp cnt[x] = cnt[i] + 1; if(cnt[x] >= n) return true; ``` # 多源最短路 ## Floyd ```cpp #include<bits/stdc++.h> using namespace std; const int N = 205, inf = 0x3f3f3f3f; int g[N][N], path[N][N]; int n, m, q; int tx, ty; void writePath(int x, int y){ if (path[x][y] != 0) { writePath(x, path[x][y]); cout << path[x][y] << " "; } if (y == ty) cout << y << " "; } void floyd() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (g[i][k] + g[k][j] < g[i][j]) { g[i][j] = g[i][k] + g[k][j]; path[i][j] = path[k][j]; } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) g[i][j] = 0; else g[i][j] = inf; } } for (int i = 0; i < m; i++) { int x, y, z; cin >> x >> y >> z; path[x][y] = x; g[x][y] = min(g[x][y], z); } floyd(); cin >> tx >> ty; cout << g[tx][ty] << endl; writePath(tx, ty); return 0; } ``` ``` ``` Last modification：January 10, 2024 © Allow specification reprint Like 0 如果觉得我的文章对你有用，请随意赞赏
Comment here is closed