結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー | tonegawa |
提出日時 | 2024-12-14 07:44:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 545 ms / 2,000 ms |
コード長 | 12,562 bytes |
コンパイル時間 | 2,924 ms |
コンパイル使用メモリ | 213,952 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-14 07:44:41 |
合計ジャッジ時間 | 8,957 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <array>#include <tuple>#include <stack>#include <queue>#include <deque>#include <algorithm>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <bitset>#include <cmath>#include <functional>#include <cassert>#include <climits>#include <iomanip>#include <numeric>#include <memory>#include <random>#include <thread>#include <chrono>#define allof(obj) (obj).begin(), (obj).end()#define range(i, l, r) for(int i=l;i<r;i++)#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))#define bit_kth(i, k) ((i >> k)&1)#define bit_highest(i) (i?63-__builtin_clzll(i):-1)#define bit_lowest(i) (i?__builtin_ctzll(i):-1)using ll = long long;using ld = long double;using ul = uint64_t;using pi = std::pair<int, int>;using pl = std::pair<ll, ll>;using namespace std;template<typename F, typename S>std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {dest << p.first << ' ' << p.second;return dest;}template<typename A, typename B>std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {dest << std::get<0>(t) << ' ' << std::get<1>(t);return dest;}template<typename A, typename B, typename C>std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);return dest;}template<typename A, typename B, typename C, typename D>std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);return dest;}template<typename T>std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {int sz = v.size();if (!sz) return dest;for (int i = 0; i < sz; i++) {int m = v[i].size();for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');}return dest;}template<typename T>std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {int sz = v.size();if (!sz) return dest;for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';dest << v[sz - 1];return dest;}template<typename T, size_t sz>std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {if (!sz) return dest;for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';dest << v[sz - 1];return dest;}template<typename T>std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {for (auto itr = v.begin(); itr != v.end();) {dest << *itr;itr++;if (itr != v.end()) dest << ' ';}return dest;}template<typename T, typename E>std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {for (auto itr = v.begin(); itr != v.end(); ) {dest << '(' << itr->first << ", " << itr->second << ')';itr++;if (itr != v.end()) dest << '\n';}return dest;}template<typename T>std::vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }template<typename T, typename... Tail>auto make_vec(size_t sz, Tail ...tail) {return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));}template<typename T>std::vector<T> read_vec(size_t sz) {std::vector<T> v(sz);for (int i = 0; i < (int)sz; i++) std::cin >> v[i];return v;}template<typename T, typename... Tail>auto read_vec(size_t sz, Tail ...tail) {auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);return v;}template<typename T, size_t size>auto make_array(T x) {std::array<T, size> res;res.fill(x);return res;}template<typename T, size_t size, size_t size2, size_t... Tail>auto make_array(T x) {std::array<decltype(make_array<T, size2, Tail...>(x)), size> res;res.fill(make_array<T, size2, Tail...>(x));return res;}// x / y以上の最小の整数ll ceil_div(ll x, ll y) {assert(y > 0);return (x + (x > 0 ? y - 1 : 0)) / y;}// x / y以下の最大の整数ll floor_div(ll x, ll y) {assert(y > 0);return (x + (x > 0 ? 0 : -y + 1)) / y;}void io_init() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);}template<typename _W>struct edge_base {using W = _W;int t;edge_base() {}edge_base(int _t) : t(_t) {}virtual int from() const {assert(false);}int to() const {return t;}virtual W weight() const {assert(false);}virtual int id() const {assert(false);}operator int() const {return t;}};struct simple_edge : edge_base<int> {simple_edge() {}simple_edge(int _t) : edge_base<int>(_t) {}int weight() const override {return 1;}int id() const override {return -1;}};struct labeled_edge : edge_base<int> {int _s, _id;labeled_edge() {}labeled_edge(int _s, int _t, int _id) : edge_base<int>(_t), _s(_s), _id(_id) {}int weight() const override {return 1;}int from() const override {return _s;}int id() const override {return _id;}};template<typename _W>struct weighted_edge : edge_base<_W> {using W = _W;W w;weighted_edge() {}weighted_edge(int _t, _W _w) : edge_base<_W>(_t), w(_w) {}W weight() const override {return w;}int id() const override {return -1;}};template<typename _W>struct weighted_labeled_edge : edge_base<_W> {using W = _W;W w;int _s, _id;weighted_labeled_edge() : _id(-1) {}weighted_labeled_edge(int _s, int _t, _W _w, int _id) : edge_base<_W>(_t), w(_w), _s(_s), _id(_id) {}int from() const override {return _s;}W weight() const override {return w;}int id() const override {return _id;}};template <class E>struct csr {std::vector<int> start;std::vector<E> elist;csr() {}explicit csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) {for (auto e : edges) {start[e.first + 1]++;}for (int i = 1; i <= n; i++) {start[i] += start[i - 1];}auto counter = start;for (auto e : edges) {elist[counter[e.first]++] = e.second;}}~csr() {}int N() const {return start.size() - 1;}int deg(int i) const {return start[i + 1] - start[i];}int begin(int i) const {return start[i];}int end(int i) const {return start[i + 1];}E& operator [] (int i) { return elist[i]; }};// 全体の最小コスト閉路// 重みあり O(V(V + E)logV)template<typename edge>struct cycle_detection_mincost {using W = typename edge::W;static constexpr W inf = std::numeric_limits<W>::max() / 2;private:csr<edge> g;std::pair<std::vector<W>, std::vector<edge>> bfs_tree(int s) {int N = g.N();std::vector<W> dist(N, inf);std::vector<edge> par(N);std::queue<int> q;q.push(s);dist[s] = 0;while (!q.empty()) {int v = q.front();q.pop();for (int i = g.begin(v); i < g.end(v); i++) {int to = g[i];if (dist[v] + 1 < dist[to]) {dist[to] = dist[v] + 1;par[to] = g[i];q.push(to);}}}return {dist, par};}std::pair<std::vector<W>, std::vector<edge>> dijkstra_tree(int s) {int N = g.N();std::vector<W> dist(N, inf);std::vector<edge> par(N);using P = std::pair<W, int>;std::priority_queue<P, std::vector<P>, std::greater<P>> q;q.push({0, s});dist[s] = 0;while (!q.empty()) {auto [d, v] = q.top();q.pop();if (dist[v] != d) continue;for (int i = g.begin(v); i < g.end(v); i++) {int to = g[i];W nd = dist[v] + g[i].weight();if (nd < dist[to]) {dist[to] = nd;par[to] = g[i];q.push({nd, to});}}}return {dist, par};}public:cycle_detection_mincost(const csr<edge> &_g) : g(_g) {}// vを含む最小閉路// 無向グラフの場合のみ辺のs-tが逆になっている場合があるがidの順序は正しい// 重みあり O((V + E)logV)// 重みなし O(V + E)std::pair<W, std::vector<edge>> find(int v, bool directed, bool weighted, bool accept_self_loop) {int N = g.N();W w = inf;int eid = -1;if (accept_self_loop) {for (int j = g.begin(v); j < g.end(v); j++) {if (g[j].to() == v && w < g[j].weight()) {w = g[j].weight();eid = j;}}}std::vector<W> dist;std::vector<edge> par;std::vector<int> semi_root;if (weighted) {std::tie(dist, par) = dijkstra_tree(v);} else {std::tie(dist, par) = bfs_tree(v);}if (directed) {for (int i = 0; i < N; i++) {if (i == v || dist[i] == inf || dist[i] > w) continue;for (int j = g.begin(i); j < g.end(i); j++) {if (g[j].to() == v && dist[i] + g[j].weight() < w) {w = dist[i] + g[j].weight();eid = j;}}}} else {semi_root.resize(N, -1);auto dfs = [&](auto &&dfs, int u, int p, int sr) -> void {semi_root[u] = sr;for (int i = g.begin(u); i < g.end(u); i++) {int to = g[i];if (to == v || to == p || to == u || dist[to] == inf) continue;if (par[to].id() == g[i].id()) {dfs(dfs, to, u, sr);}}};for (int i = 0; i < N; i++) {if (i == v || dist[i] == inf) continue;if (par[i].from() == v) dfs(dfs, i, v, i);}for (int i = 0; i < N; i++) {if (i == v || dist[i] == inf || dist[i] > w) continue;for (int j = g.begin(i); j < g.end(i); j++) {int to = g[j];if (g[j].id() == par[i].id()) continue;if (semi_root[i] == semi_root[to]) continue;if (dist[i] + dist[to] + g[j].weight() < w) {w = dist[i] + dist[to] + g[j].weight();eid = j;}}}}//return {w, {}};if (w == inf) return {inf, {}};std::vector<edge> res;res.push_back(g[eid]);int u = g[eid].from();while (u != v) {res.push_back(par[u]);u = par[u].from();}std::reverse(res.begin(), res.end());if (!directed) {u = g[eid].to();while (u != v) {res.push_back(par[u]);u = par[u].from();}}return {w, res};}};int main() {io_init();int T;std::cin >> T;int N, M;std::cin >> N >> M;using edge = weighted_labeled_edge<long long>;std::vector<std::pair<int, edge>> E;for (int i = 0; i < M; i++) {int a, b, c;std::cin >> a >> b >> c;a--, b--;E.push_back({a, {a, b, c, i}});if (T == 0) {E.push_back({b, {b, a, c, i}});}}cycle_detection_mincost<edge> G(csr<edge>(N, E));auto inf = G.inf;long long w = inf;for (int i = 0; i < N; i++) {w = std::min(w, G.find(i, T, true, true).first);}std::cout << (w == inf ? -1 : w) << '\n';}