51 lines
1.3 KiB
C++
51 lines
1.3 KiB
C++
// P3371：非负边权的单源最短路，邻接表朴素实现。
|
|
// C++11；时间 O(n*n+m)，空间 O(n+m)。
|
|
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
using ll = long long;
|
|
|
|
struct Edge {
|
|
int to;
|
|
ll w;
|
|
};
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
int n, m, s;
|
|
if (!(cin >> n >> m >> s)) return 0;
|
|
vector<vector<Edge>> g(n + 1);
|
|
for (int i = 0; i < m; ++i) {
|
|
int u, v;
|
|
ll w;
|
|
cin >> u >> v >> w;
|
|
g[u].push_back({v, w});
|
|
}
|
|
const ll INF = (1LL << 60);
|
|
vector<ll> dis(n + 1, INF);
|
|
vector<bool> used(n + 1, false);
|
|
dis[s] = 0; // 源点可一步不走；其他点尚未找到路线。
|
|
for (int round = 0; round < n; ++round) {
|
|
int u = -1;
|
|
for (int v = 1; v <= n; ++v) {
|
|
if (!used[v] && (u == -1 || dis[v] < dis[u])) {
|
|
u = v;
|
|
}
|
|
}
|
|
// 最小候选都不可达时，其余未确定点也不可达。
|
|
if (u == -1 || dis[u] == INF) break;
|
|
used[u] = true;
|
|
for (const Edge& e : g[u]) {
|
|
ll nd = dis[u] + e.w;
|
|
if (nd < dis[e.to]) dis[e.to] = nd;
|
|
}
|
|
}
|
|
for (int v = 1; v <= n; ++v) {
|
|
if (v > 1) cout << ' ';
|
|
cout << (dis[v] == INF ? 2147483647LL : dis[v]);
|
|
}
|
|
cout << '\n';
|
|
return 0;
|
|
}
|