C语言 【C with STL】 单源最短路之SPFA算法

[JiansYuan]

呃呃呃
[MD] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 10005; const int INF = 0x3f3f3f; vector<pair<int, int> > g[N]; int d[N], cnt[N]; bool vis[N]; int main(){ int n, m, s; scanf("%d %d %d", &n, &m, &s); for(int i = 0; i < m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); g[u].push_back({v, w}); } for(int i = 1; i <= n; i++) { vis[i] = false; d[i] = INF; cnt[i] = 0; } d[s] = 0; queue<int> q; q.push(s); bool flag = false; while(q.size()) { int u = q.front(); q.pop(); vis[u] = false; for(auto i : g[u]) { int v = i.first, w = i.second; if(d[v] > d[u] + w){ d[v] = d[u] + w; cnt[v]++; if(cnt[v] > n) flag = true; if(!vis[v]){ vis[v] = true; q.push(v); } } } } if(flag) printf("ERROR!\n"); else for(int i=1;i<=n;i++) printf("%d ", d[i]); return 0; } ``` [/i][/u][/u][/u][/u][/s][/i][/i][/i][/u][/MD]