結果
問題 | No.2914 正閉路検出 |
ユーザー |
![]() |
提出日時 | 2024-10-05 10:15:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 4,976 bytes |
コンパイル時間 | 3,102 ms |
コンパイル使用メモリ | 268,272 KB |
実行使用メモリ | 36,832 KB |
最終ジャッジ日時 | 2024-10-05 10:16:03 |
合計ジャッジ時間 | 13,032 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for(long long i = 0; i < n; i++) #define ALL(v) (v).begin(), (v).end() using namespace std; using lint = long long; template <class T = long long> struct WeightedUnionFind { private: int n; vector<int> par; vector<T> diff_weight; public: WeightedUnionFind() {} WeightedUnionFind(int n_) : n(n_), par(n, -1), diff_weight(n, T(0)) {} int leader(int x) { assert(0 <= x && x < n); if (par[x] < 0) { return x; } else { int r = leader(par[x]); diff_weight[x] += diff_weight[par[x]]; return par[x] = r; } } T weight(int x) { assert(0 <= x && x < n); leader(x); return diff_weight[x]; } T diff(int x, int y) { assert(0 <= x && x < n); assert(0 <= y && y < n); return weight(y) - weight(x); } int merge(int x, int y, T w) { assert(0 <= x && x < n); assert(0 <= y && y < n); w += weight(x); w -= weight(y); x = leader(x); y = leader(y); if (x == y) { return x; } if (-par[x] < -par[y]) { swap(x, y); w *= T(-1); } par[x] += par[y]; par[y] = x; diff_weight[y] = w; return x; } bool same(int x, int y) { assert(0 <= x && x < n); assert(0 <= y && y < n); return leader(x) == leader(y); } int size(int x) { assert(0 <= x && x < n); return -par[leader(x)]; } vector<vector<int>> groups() { vector<vector<int>> member(n); for (int i = 0; i < n; i++) { member[leader(i)].emplace_back(i); } vector<vector<int>> res; for (int i = 0; i < n; i++) { if (member[i].size() > 0) { res.emplace_back(member[i]); } } return res; } }; template <class T> struct Edge { int from, to; T cost; int idx; Edge() {} Edge(int to_) : to(to_) {} Edge(int to_, T cost_) : to(to_), cost(cost_) {} Edge(int from_, int to_, int idx_) : from(from_), to(to_), idx(idx_) {} Edge(int from_, int to_, T cost_, int idx_) : from(from_), to(to_), cost(cost_), idx(idx_) {} }; template <class T> using Graph = vector<vector<Edge<T>>>; using graph = Graph<long long>; using edge = Edge<long long>; #define add emplace_back struct Dijkstra { private: graph g; int n, s; vector<long long> d; vector<edge> prev; vector<bool> visit; priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; public: Dijkstra(graph g_, int s_) : g(g_), n(g.size()), s(s_), d(n, 1000000000000000000), prev(n), visit(n, false) { d[s] = 0LL; pq.emplace(d[s], s); while (!pq.empty()) { int v = pq.top().second; pq.pop(); if (visit[v]) { continue; } visit[v] = true; for (auto e : g[v]) { int nv = e.to; long long nc = e.cost; if (d[nv] > d[v] + nc) { d[nv] = d[v] + nc; prev[nv] = e; pq.emplace(d[nv], nv); } } } } vector<long long> dists() { return d; } long long dist(int t) { return d[t]; } vector<edge> route(int t) { if (s == t || d[t] == 1000000000000000000) { return {}; } vector<edge> res; int cur = t; while (cur != s) { res.emplace_back(prev[cur]); cur = prev[cur].from; } reverse(res.begin(), res.end()); return res; } }; int main() { int n, m; cin >> n >> m; WeightedUnionFind uf(n); graph g(n); int s = -1, t = -1, id = -1; rep(i, m) { int u, v; lint w; cin >> u >> v >> w; u--; v--; if (!uf.same(u, v)) { uf.merge(v, u, w); g[u].add(u, v, w, i); g[v].add(v, u, w, i); } else { lint d = uf.diff(v, u); if (d == w) { uf.merge(v, u, w); g[u].add(u, v, w, i); g[v].add(v, u, w, i); } else if (d > w) { s = u; t = v; id = i; break; } else { s = v; t = u; id = i; break; } } } if (s >= 0) { auto r = Dijkstra(g, s).route(t); cout << r.size() + 1 << endl << s + 1 << endl; for (auto e : r) { cout << e.idx + 1 << " "; } cout << id + 1 << endl; return 0; } cout << -1 << endl; }