spfa
#include <stdio.h> #include <queue> using namespace std; #define inf 2147483647 const int maxn = 10010, maxm = 500050; int n, m, s; struct edge { int to, weight, next; }; edge edges[maxm]; int head[maxn], edge_cnt; void add(int x, int y, int w) { edges[++edge_cnt].next = head[x]; edges[edge_cnt].to = y; edges[edge_cnt].weight = w; head[x] = edge_cnt; } long long dist[maxn]; int inque[maxn]; void spfa() { for (int i = 1; i <= n; ++i) dist[i] = inf; dist[s] = 0; queue<int> q; q.push(s); inque[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); inque[u] = 0; for (int i = head[u]; i != 0; i = edges[i].next) { int v = edges[i].to, w = edges[i].weight; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (!inque[v]) { q.push(v); inque[v] = 1; } } } } } int main() { scanf("%d %d %d", &n, &m, &s); for (int i = 1; i <= m; ++i) { int x, y, w; scanf("%d %d %d", &x, &y, &w); add(x, y, w); } spfa(); for (int i = 1; i <= n; ++i) printf("%lld ", dist[i]); return 0; }
算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题