洛谷:p3371
#include <iostream> #include <vector> #include <stack> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <cstring> #include <unordered_map> #include <unordered_set> #include <algorithm> #include <numeric> #include <chrono> #include <ctime> #include <cmath> #include <cctype> #include <string> #include <cstdio> #include <iomanip> #include <thread> #include <mutex> #include <condition_variable> #include <functional> #include <iterator> using namespace std; const int MAXN = 1e5 + 7; const int MAXM = 5e5 + 7; const int INF = 0x7fffffff; struct Point { int to, next, w; Point() :to(0), next(0), w(0) {} }points[MAXM]; int heads[MAXN] = { 0 }, visit[MAXN] = { 0 }, d[MAXN] = { 0 }, p[MAXN] = { 0 }, cnt[MAXN] = {0},n, m, s, nCount = 0; void AddEdge(int from ,int to, int w) { points[++nCount].to = to; points[nCount].w = w; points[nCount].next = heads[from]; heads[from] = nCount; } bool BellmanFord(int s) { queue<int> q; for (int i = 1; i <= n; ++i) d[i] = INF; d[s] = 0; visit[s] = true; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); visit[u] = false; for (int i = heads[u]; i; i = points[i].next) { int v = points[i].to; int w = points[i].w; if (d[u] < INF && d[v] > d[u] + w) { d[v] = d[u] + w; p[v] = u; if (!visit[v]) { q.push(v); visit[v] = true; if (++cnt[v] > n) return false; } } } } return true; } int main() { cin >> n >> m >> s; int from ,to ,w; for (int i = 0; i < m; i++) { cin >> from >> to >> w; AddEdge(from, to, w); } BellmanFord(s); for (int i = 1; i <= n; ++i) cout << d[i] << " "; return 0; }