結果
問題 |
No.2914 正閉路検出
|
ユーザー |
|
提出日時 | 2024-10-04 23:16:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,719 bytes |
コンパイル時間 | 2,197 ms |
コンパイル使用メモリ | 207,916 KB |
最終ジャッジ日時 | 2025-02-24 15:37:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 WA * 1 MLE * 1 -- * 50 |
ソースコード
#include<bits/stdc++.h> using namespace std; int main () { int N, M; cin >> N >> M; using ll = long long; using T = tuple<int, int, ll>; std::vector<T> gr[200020]; int E[200020]; for (int i = 1; i <= M; i ++) { int u, v; ll w; cin >> u >> v >> w; gr[u].emplace_back(v, i, w); gr[v].emplace_back(u, i, -w); E[i] = u ^ v; } ll D[200020]; int pre [200020]; fill(D, D + (N + 1), 0); fill(pre, pre + (N + 1), 0); for (int i = 1; i <= N; i ++) { if (pre[i]) continue; pre[i] = -1; queue<int>que; que.push(i); int beg = -1; int pr2 = -1; ll d2 = -1; while (!que.empty()) { int u = que.front(); que.pop(); for (auto& [v, i, d] : gr[u]) { if (!pre[v]) { pre[v] = i; D[v] = D[u] + d; que.push(v); } else if (D[v] != D[u] + d) { beg = v; pr2 = i; d2 = D[u] + d; break; } } if (beg != -1) break; } if (beg != -1) { ll d1 = D[beg]; vector<int> a1, a2; int fl = beg; while (fl != i) { a1.push_back(pre[fl]); fl = fl ^ E[pre[fl]]; } a2.push_back(pr2); fl = fl ^ E[pr2]; while (fl != i) { a2.push_back(pre[fl]); fl = fl ^ E[pre[fl]]; } if (d1 > d2) { swap(a1, a2); } reverse(a2.begin(), a2.end()); for (auto& a : a2) { a1.push_back(a); } bool ex[200020]; a2.clear(); for (auto& a : a1) { if (ex[a]) { while (ex[a]) { ex[a2.back()] = false; a2.pop_back(); } } else { ex[a] = true; a2.push_back(a); } } cout << a2.size() << endl; cout << beg << endl; for (int i = 0; i < a2.size(); i ++) { cout << a2[i] << (i + 1 < a2.size() ? " " : ""); } cout << endl; return 0; } } puts("-1"); }