題意#
給你一張有向圖，你的任務是判斷這張圖裡面到底有沒有「負環」（Negative Cycle）。
負環的意思就是圖中存在一個迴圈，繞這個迴圈走一圈的總權重加起來是負數。如果圖中存在負環，不但要輸出 YES，還要順便印出這個負環的具體路徑（任意一個即可）；如果沒有負環，就輸出 NO。
思路#
要找圖上的負環，也就是要處理帶有負權重的最短路徑問題，通常我們的首選會是 Bellman-Ford 或是它的佇列優化版演算法 SPFA（Shortest Path Faster Algorithm）。
在普通的圖上，兩點之間的最短路徑最多只會經過 \(n-1\) 條邊。
如果在執行 SPFA 的過程中，我們發現某個節點被推入佇列鬆弛的次數達到了 \(n\) 次，那就代表我們不小心掉進了一個不斷讓權重減少的無限迴圈裡，這個迴圈就是所謂的負環。
找出負環後，接下來的挑戰是如何回推這條路徑。
我們可以在鬆弛時建立一個 path 陣列來記錄每個節點是「從哪個節點走過來的」。當抓到某個點的更新次數達標（也就是卷進負環的點）時，我們就可以沿著 path 一路往回追溯。
為了確保我們真的是走在環上，可以用一個 inst 陣列記錄走過的點，當發現我們走到了之前走過的點，那個點就是負環的起點兼終點。
最後只需要透過堆疊（Stack）把這段路徑倒出來，就能得到正確的順序了。
特別要注意的是，因為這張圖可能並非完全連通，負環也許藏在我們從節點 1 出發根本無法到達的某個孤立角落。因此，保險起見我們最好掃過一次所有的節點，當作起點分別去尋找看看。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, m; cin >> n >> m;
vector<vector<PII>> g(n+1);
while (m--) {
int a, b, w;
cin >> a >> b >> w;
g[a].pb({b, w}); // 建立有向圖
}
int hasCycle = 0, ed;
// 因為圖可能不連通，因此嘗試將每個點都當成起點找一遍負環
for (int i = 1; i <= n && !hasCycle; i++) {
vector<int> dis(n+1, INF), vis(n+1), cnt(n+1), path(n+1);
queue<int> q;
q.push(i); dis[i] = 0; vis[i] = 1; path[i] = -1;
while (q.size() && !hasCycle) {
int nowID = q.front(); q.pop();
vis[nowID] = 0; // 標記為不在佇列內
for (auto [toID, toDist] : g[nowID]) {
// 如果能鬆弛更新距離
if (dis[toID] > dis[nowID] + toDist) {
// 如果這個點被更新的次數 >= n 次，代表一定有負環
if (++cnt[toID] >= n) {
hasCycle = 1;
ed = toID; // 記錄捲入負環的點
path[toID] = nowID;
break;
}
dis[toID] = dis[nowID] + toDist;
// 如果節點不在佇列中，就把它推回佇列等待下一輪幫別人更新
if (!vis[toID]) q.push(toID), vis[toID] = 1;
path[toID] = nowID; // 記錄來源
}
}
}
// 如果在這輪中找到了負環
if (hasCycle) {
cout << "YES\n";
stack<int> st;
vector<int> inst(n+1);
// 沿著來源路徑倒退走，直到走到重複的節點為止
while (!inst[ed]) {
inst[ed] = 1;
st.push(ed);
ed = path[ed];
}
// 印出迴圈路徑
cout << ed;
while (st.top() != ed) { // 將堆疊裡的節點依序倒出直至接回起點
cout << ' ' << st.top();
st.pop();
}
cout << ' ' << ed;
}
}
if (!hasCycle) cout << "NO\n";
}
