結果
問題 | No.2914 正閉路検出 |
ユーザー |
|
提出日時 | 2024-10-04 23:35:04 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,906 bytes |
コンパイル時間 | 7,782 ms |
コンパイル使用メモリ | 270,788 KB |
最終ジャッジ日時 | 2025-02-24 15:41:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 RE * 13 |
ソースコード
#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, p, d] : gr[u]) {// cout << v << " " << i << " " << d << endl;if (!pre[v]) {pre[v] = p;D[v] = D[u] + d;que.push(v);} else if (D[v] != D[u] + d) {beg = v;pr2 = p;d2 = D[u] + d;break;}}if (beg != -1) break;}if (0) {for (int j = 1; j <= N; j ++) {cout << D[j] << " ";}cout << endl;}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 = beg ^ 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) {// cout << a<< " ";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");}