2 条题解
-
0
SPFA
// SPFA #include <bits/stdc++.h> using namespace std; const int MAXN = 10000; const int MAXM = 500000; const int INF = 2147483647; int n, m, s; // <终点,边权> vector<pair<int, int>> e[MAXN + 5]; int dis[MAXN + 5]; // SPFA queue<int> q; // 记录在不在队列里 // 如果要判断负环，还要记录入队次数 bool vis[MAXN + 5]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u].push_back(make_pair(v, w)); } // SPFA q.push(s); for (int i = 1; i <= n; i++) dis[i] = INF; dis[s] = 0; vis[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; // 只松弛以 u 为起点的边 for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int w = e[u][i].second; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v); vis[v] = true; } } } } for (int i = 1; i <= n; i++) cout << dis[i] << " "; return 0; } -
0
33DAI LV 7 (1/1) @ 2025-2-22 11:57:02
Bellman-Ford
// bellman-ford #include <bits/stdc++.h> using namespace std; const int MAXN = 10000; const int MAXM = 500000; const int INF = 2147483647; int n, m, s; int u[MAXM + 5], v[MAXM + 5], w[MAXM + 5]; int dis[MAXN + 5]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= n; i++) dis[i] = INF; for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i]; dis[s] = 0; // 为了避免记错，干脆做 n 次，如果做完还能做，说明有负环 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int U = u[j]; int V = v[j]; int W = w[j]; if (dis[U] != INF) { if (dis[V] == INF || dis[U] + W < dis[V]) dis[V] = dis[U] + W; } } } for (int i = 1; i <= n; i++) cout << dis[i] << " "; return 0; }
- 1
