SPFA 板子求条
  • 板块学术版
  • 楼主__xsy2013__
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/13 14:54
  • 上次更新2024/4/13 16:31:14
查看原帖
SPFA 板子求条
575714
__xsy2013__楼主2024/4/13 14:54
// By @xusiyaun
// In YUANSHIREN
// C++

# include <bits/stdc++.h>
# define N 2010
# define M 12010
# define inf 0x3f3f3f3f

using namespace std;

int head[N], ver[M], edge[M], Next[M], n, m, tot;
int dist[N], cnt[N];
bool vis[N];
queue <int> Q;

void ADD(int x, int y, int z) {
	ver[++tot] = y;
	edge[tot] = z;
	Next[tot] = head[x];
	head[x] = tot;
}

bool SPFA(int root) {
	memset(vis, 0, sizeof(vis));
	memset(cnt, 0, sizeof(cnt));
	vis[root] = 1;
	Q.push(root);
	while(Q.size()) {
		int x = Q.front();
		vis[x] = 0;
		Q.pop();
		for(int i = head[x]; ~i; i = Next[i]) {
			int y = ver[i];
			if(dist[y] > dist[x] + edge[i]) {
				dist[y] = dist[x] + edge[i];
				cnt[y] = cnt[x] + 1;
				if(cnt[y] >= (n + 1)) return true;
				if(!vis[y]) {
					Q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
	return false;
}

int main() {

	memset(head, -1, sizeof(head));
	tot = -1;
	int x, y, z;
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> x >> y >> z;
		ADD(x, y, z);
	}

	for(int i = 1; i <= n; i++) {
		ADD(n + 1, i, 0);
	}
	n++;
	if(SPFA(n + 1)) cout << "Yes";
	else cout << "No";
	return 0;
}

2024/4/13 14:54
加载中...