确实
by NCUJACK @ 2024-03-16 10:41:30
大佬我用的bellman-ford应该就是单纯的TLE了吧
```cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int n, m, st = 0;
vector< pair<int, int> > g[5005];
int dist[5005];
bool bell() {
memset(dist, 127, sizeof(dist));
dist[st] = 0;
for (int i = 1, up = m + n; i < up; ++ i) {
for (int j = 1; j <= n; ++ j) {
for (auto k : g[j]) {
int x = j, y = k.first, v = k.second;
if (dist[y] < (1 << 30) && dist[y] + v < dist[x]) dist[x] = dist[y] + v;
}
}
}
bool ok = true;
for (int i = 1; i <= n; ++ i) {
for (auto j : g[i]) {
int x = i, y = j.first, v = j.second;
if (dist[y] < (1 << 30) && dist[y] + v < dist[x]) {
ok = false;
break;
}
}
if (!ok) break;
}
return ok;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++ i) {
g[i].push_back({st, 0});
}
for (int i = 1; i <= m; ++ i) {
int x, y, v;
cin >> x >> y >> v;
g[y].push_back({x, v});
}
if (bell()) {
for (int i = 1; i <= n; ++ i) {
cout << -dist[i] << ' ';
}
} else {
cout << "NO";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
solve();
}
```
by AC_Yee @ 2024-04-04 17:08:21