2 条题解
-
0
单源最短路
朴素版 dijkstra
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2500 + 1, INF = 0x3f3f3f3f, MOD = 1E9 + 7; int n, m, g[N][N], dis[N], st[N]; void dijkstra(int s) { memset(dis, 0x3f, sizeof dis); dis[s] = 0; for (int i = 1; i <= n; i++) { int u = -1; for (int j = 1; j <= n; j++) if (!st[j] && (u == -1 || dis[u] > dis[j])) u = j; if (u == -1) break; // 可省略 st[u] = 1; for (int j = 1; j <= n; j++) dis[j] = min(dis[j], dis[u] + g[u][j]); } } int main(int argc, char* argv[]) { memset(g, 0x3f, sizeof g); // memset <cstring> 8bit 0x3f = 0011 1111 // 0x3f3f3f3f = 0011 1111 0011 1111 0011 1111 0011 1111 = 1e9. int s, t, u, v, w; cin >> n >> m >> s >> t; for (int i = 1; i <= m; i++) { cin >> u >> v >> w; g[u][v] = g[v][u] = min(g[u][v], w); } dijkstra(s); // s -> all 单源最短路 cout << dis[t]; return 0; } -
0
hellohebin @ 2024-10-23 7:33:03
单源最短路
朴素版 dijkstra
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define PII pair<int, int> const int N = 2501, M = 6200<<1|1; class T { public: int u, v, w; T() {} T(int _v, int _w) : v(_v), w(_w) {} T(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {} bool operator<(const T& r) const { return w < r.w; } } edge[M]; int n, m, dis[N], p[N]; vector<pair<int, int>> G[N]; int f[N][N]; bool st[N]; /*------------------------------*/ void bellman_fored(int s, int t) { memset(dis, 0x3f, sizeof dis); dis[s] = 0; for (int i = 1; i < n; i++) { for (int j = 1; j <= m; j++) { int u = edge[j].u, v = edge[j].v, w = edge[j].w; dis[v] = min(dis[v], dis[u] + w); } } printf("%d\n", dis[t]); } void SPFA(int s, int t) { memset(dis, 0x3f, sizeof dis); memset(st, 0x00, sizeof st); queue<int> q; q.push(s), st[s] = 1, dis[s] = 0; while (q.size()) { int u = q.front(); q.pop(), st[u] = 0; for (auto it : G[u]) { int v = it.first, w = it.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.push(v), st[v] = 1; } } } printf("%d\n", dis[t]); } void dijkstra(int s, int t) { memset(dis, 0x3f, sizeof dis); memset(st, 0x00, sizeof st); dis[s] = 0; for (int i = 1; i <= n; i++) { int u = -1; for (int j = 1; j <= n; j++) if (!st[j] && (u == -1 || dis[j] < dis[u])) u = j; if (u == -1) break; st[u] = 1; for (auto it : G[u]) { int v = it.first, w = it.second; dis[v] = min(dis[v], dis[u] + w); } } printf("%d\n", dis[t]); } void pri_dijkstra(int s, int t) { memset(dis, 0x3f, sizeof dis); memset(st, 0x00, sizeof st); priority_queue<PII> q; q.push({0, s}), dis[s] = 0; while (q.size()) { int u = q.top().second; q.pop(); if (st[u]) continue; st[u] = true; for (auto it : G[u]) { int v = it.first, w = it.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.push(make_pair(-dis[v], v)); } } } printf("%d\n", dis[t]); } void set_dijkstra(int s, int t) { memset(dis, 0x3f, sizeof dis); memset(st, 0x00, sizeof st); set<PII> q; q.insert(make_pair(0, s)), dis[s] = 0; while (q.size()) { int u = q.begin()->second; q.erase(q.begin()); if (st[u]) continue; st[u] = true; for (auto it : G[u]) { int v = it.first, w = it.second; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.insert(make_pair(dis[v], v)); } } } printf("%d\n", dis[t]); } void floyed(int s, int t) { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); printf("%d\n", f[s][t]); } /*------------------------------*/ int find(int u) { return u == p[u] ? u : p[u] = find(p[u]); } void kruskal() { sort(edge + 1, edge + 1 + n); for (int i = 1; i <= n; i++) p[i] = i; int tt = 0, ans = 0; for (int i = 1; i <= m; i++) { int u = edge[i].u, v = edge[i].v, w = edge[i].w; int x = find(u), y = find(v); if (x != y) { ++tt, p[x] = y, ans += w; } } printf("%d\n", tt == n - 1 ? ans : -1); } void prim() { memset(dis, 0x3f, sizeof dis); memset(st, 0x00, sizeof st); dis[1] = 0; int tt = 0, ans = 0; for (int i = 1; i <= n; i++) { int u = -1; for (int j = 1; j <= n; j++) if (!st[j] && (u == -1 || dis[u] > dis[j])) u = j; if (u == -1) break; ++tt, ans += dis[u], st[u] = 1; for (auto it : G[u]) { int v = it.first, w = it.second; dis[v] = min(dis[v], dis[u] + w); } } printf("%d\n", tt == n ? ans : -1); } /*------------------------------*/ int main() { memset(f, 0x3f, sizeof f); int u, v, w, s, t; scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &u, &v, &w); f[u][v] = f[v][u] = min(f[u][v], w); edge[i] = {u, v, w}, edge[m + i] = {v, u, w}; G[u].push_back({v, w}), G[v].push_back({u, w}); } m <<= 1; // printf("bellman_fored: "), // bellman_fored(s, t); // printf("SPFA : "), // SPFA(s, t); // printf("dijkstra : "), dijkstra(s, t); // printf("pri_dijkstra : "), // pri_dijkstra(s, t); // printf("set_dijkstra : "), // set_dijkstra(s, t); // printf("floyed : "), // floyed(s, t); // printf("kruskal : "), kruskal(); // printf("prim : "), prim(); }
- 1
信息
- ID
- 621
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 233
- 已通过
- 101
- 上传者
-