我正在实现 Bellman Ford 算法,其中输入是一个有向加权图,输出要么是 1(存在负环),要么是 0(没有负环)。
我理解 Bellman Ford 算法,并已经在许多测试用例上运行了以下代码,但似乎无法通过我想要提交的平台上的所有测试用例。我无法看到代码失败的特定测试用例。
任何提示可能出错的地方都将非常有帮助
约束条件
1 ≤ n ≤ 10^3,0 ≤ m ≤ 10^4,边权重为绝对值最多为 10^3 的整数。 (n = 顶点数, m = 边数)
代码
#include <iostream>
#include <limits>
#include <vector>
using std::cout;
using std::vector;
int negative_cycle(vector<vector<int>> &adj, vector<vector<int>> &cost) {
vector<int> dist(adj.size(), std::numeric_limits<int>::max());
dist[0] = 0;
for (int i = 0; i < adj.size() - 1; i++) {
for (int j = 0; j < adj.size(); j++) {
for (int k = 0; k < adj[j].size(); k++) {
if (dist[j] != std::numeric_limits<int>::max()) {
if ((dist[adj[j][k]] > dist[j] + cost[j][k])) {
dist[adj[j][k]] = dist[j] + cost[j][k];
}
}
}
}
}
for (int j = 0; j < adj.size(); j++) {
for (int k = 0; k < adj[j].size(); k++) {
if (dist[j] != std::numeric_limits<int>::max()) {
if ((dist[adj[j][k]] > dist[j] + cost[j][k])) {
return 1; // negative cycle
}
}
}
}
return 0; // no negative cycle
}
int main() {
int n, m;
std::cin >> n >> m;
vector<vector<int>> adj(n, vector<int>());
vector<vector<int>> cost(n, vector<int>());
for (int i = 0; i < m; i++) {
int x, y, w;
std::cin >> x >> y >> w;
adj[x - 1].push_back(y - 1);
cost[x - 1].push_back(w);
}
std::cout << negative_cycle(adj, cost);
}