P5960 【模板】差分约束算法

#include <bits/stdc++.h>
using namespace std;
int n, m;
int d[10005];
int cnt[10005];
bool vis[10005];
struct node {
	int v;
	int w;
	node (){
		
	}
	node (int vv, int ww) {
		v = vv;
		w = ww;
	}
};
vector<node> g[10005];
bool spfa() {
	queue<int> q;
	q.push(0);
	d[0] = 0;
	vis[0] = true;
	cnt[0]++;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < g[now].size(); i++) {
			int u = g[now][i].v;
			int w = g[now][i].w;
			if (d[u] > d[now] + w) {
				d[u] = d[now] + w;
				if (!vis[u]) {
					q.push(u);
					vis[u] = true;
					++cnt[u];
					if (cnt[u] > n + 1) {
						return true;
					}
					
				}
			}
		}		
	}
	return false;
}
int main(){
	scanf("%d%d", &n, &m);
	memset(d, 0x3f, sizeof(d));
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[v].push_back(node(u, w));
	}
	for (int i = 1; i <= n; i++) {
		g[0].push_back(node(i, 0));
	}
	if (!spfa()) {
		for (int i = 1; i <= n; i++) {
			printf("%d ", d[i]);
		}
	}
	return 0;
}