結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
|
提出日時 | 2024-08-15 21:15:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,312 ms / 2,000 ms |
コード長 | 9,263 bytes |
コンパイル時間 | 2,683 ms |
コンパイル使用メモリ | 197,104 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-08-15 21:15:56 |
合計ジャッジ時間 | 18,969 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
コンパイルメッセージ
main.cpp: In member function 'void dijkstra<T>::run(graph<T>&, int)': main.cpp:135:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 135 | auto [d, v] = que.top(); | ^
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#define all(a) (a).begin(), (a).end()#define pb push_back#define fi first#define se secondmt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());const ll MOD1000000007 = 1000000007;const ll MOD998244353 = 998244353;const ll MOD[3] = {999727999, 1070777777, 1000000007};const ll LINF = 1LL << 60LL;const int IINF = (1 << 30) - 2;template<typename T>struct edge{int from;int to;T cost;int id;edge(){}edge(int to, T cost=1) : from(-1), to(to), cost(cost){}edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){}edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}void reverse(){swap(from, to);}};template<typename T>struct edges : std::vector<edge<T>>{void sort(){std::sort((*this).begin(),(*this).end(),[](const edge<T>& a, const edge<T>& b){return a.cost < b.cost;});}};template<typename T = bool>struct graph : std::vector<edges<T>>{private:int n = 0;int m = 0;edges<T> es;bool dir;public:graph(int n, bool dir) : n(n), dir(dir){(*this).resize(n);}void add_edge(int from, int to, T cost=1){if(dir){es.push_back(edge<T>(from, to, cost, m));(*this)[from].push_back(edge<T>(from, to, cost, m++));}else{if(from > to) swap(from, to);es.push_back(edge<T>(from, to, cost, m));(*this)[from].push_back(edge<T>(from, to, cost, m));(*this)[to].push_back(edge<T>(to, from, cost, m++));}}int get_vnum(){return n;}int get_enum(){return m;}bool get_dir(){return dir;}edge<T> get_edge(int i){return es[i];}edges<T> get_edge_set(){return es;}};template<typename T>struct redge{int from, to;T cap, cost;int rev;redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}};template<typename T> using Edges = vector<edge<T>>;template<typename T> using weighted_graph = vector<Edges<T>>;template<typename T> using tree = vector<Edges<T>>;using unweighted_graph = vector<vector<int>>;template<typename T> using residual_graph = vector<vector<redge<T>>>;template<typename T>struct dijkstra{private:const T TINF = numeric_limits<T>::max()/2;int n, s;graph<T> G;vector<T> dist;vector<int> vpar;edges<T> epar;public:dijkstra(graph<T> G, int s) : G(G), s(s){// initilizationn = G.get_vnum();dist.resize(n, TINF);vpar.resize(n, -1);epar.resize(n);// running Dijkstra algorithmrun(G, s);}void run(graph<T> &G, int s){dist[s] = 0;priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> que;que.push({0, s});while(!que.empty()){auto [d, v] = que.top();que.pop();if(dist[v] < d) continue;for(auto e : G[v]){if(dist[v] + e.cost < dist[e.to]){dist[e.to] = dist[v] + e.cost;vpar[e.to] = v;epar[e.to] = e;que.push({dist[e.to], e.to});}}}}T get_dist(int t){return dist[t];}vector<T> get_dist(){return dist;}vector<int> get_vpar(){return vpar;}int get_vpar(int v){return vpar[v];}edges<T> get_epar(){return epar;}edge<T> get_epar(int v){return epar[v];}vector<int> get_vpath(int t){vector<int> vpath;int cur = t;while(cur != -1){vpath.push_back(cur);cur = vpar[cur];}reverse(vpath.begin(), vpath.end());return vpath;}edges<T> get_epath(int t){edges<T> epath;int cur = t;while(cur != s){epath.push_back(epar[cur]);cur = vpar[cur];}reverse(epath.begin(), epath.end());return epath;}graph<T> get_shotest_path_tree(){graph<T> spt(n, false);for(int v=0; v<n; v++) if(v != s){int p = vpar[v];auto e = G.get_edge(epar[v]);spt[vpar[v]].add_edge(vpar[v], v, e.cost);}return spt;}};struct cycle{template<typename S>static edges<S> find_cycle(graph<S> &G){int n = G.get_vnum();vector<int> used(n, 0);edges<S> cyc;function<bool(int, int)> dfs = [&](int v, int e_id){for(auto e : G[v]) if(e.id != e_id){if(used[e.to]==1){cyc.push_back(e);return true;}else if(used[e.to]==0){used[e.to] = used[v];if(dfs(e.to, e.id)){cyc.push_back(e);return true;}}}used[v] = 2;return false;};for(int v=0; v<n; v++) if(used[v]==0){used[v] = 1;if(dfs(v, -1)) break;}if(cyc.empty()) return cyc;while(cyc.back().from != cyc[0].to) cyc.pop_back();reverse(cyc.begin(), cyc.end());return cyc;}template<typename T>static edges<T> find_oddcycle(graph<T> &G, int s){}template<typename T>static edges<T> find_evencycle(graph<T> &G, int s){}template<typename S>static edges<S> find_mincostcycle(graph<S> &G, int s){int n = G.get_vnum();const S SINF = numeric_limits<S>::max()/2;bool dir = G.get_dir();dijkstra<S> dijk(G, s);auto dist = dijk.get_dist();edges<S> cyc;// find minimum cost cycle on directed graphif(dir){S cost = SINF;edge<S> emin;for(int v=0; v<n; v++) for(auto e : G[v]) if(e.to == s){if(dist[v] + e.cost < cost){cost = dist[v] + e.cost;emin = e;}}if(cost == SINF) return {};cyc = dijk.get_epath(emin.from);cyc.push_back(emin);}// find minimum cost cycle on undirected graphif(!dir){vector<vector<int>> ch(n);for(int v=0; v<n; v++) if(v != s && dijk.get_vpar(v)!=-1){ch[dijk.get_vpar(v)].push_back(v);}vector<int> label(n, -1);label[s] = s;function<void(int, int)> labeling = [&](int v, int l){label[v] = l;for(int to : ch[v]) labeling(to, l);};for(int to : ch[s]) labeling(to, to);S cost = SINF;edge<S> emin;for(int v=0; v<n; v++) if(v != s) for(auto e : G[v]){if(e.id != dijk.get_epar(v).id && label[v] != label[e.to] && dist[v] + dist[e.to] + e.cost < cost){cost = dist[v] + dist[e.to] + e.cost;emin = e;}}if(cost == SINF) return {};cyc = dijk.get_epath(emin.from);cyc.push_back(emin);auto epath = dijk.get_epath(emin.to);reverse(epath.begin(), epath.end());for(auto e : epath){e.reverse();cyc.push_back(e);}}return cyc;}template<typename S>static edges<S> find_mincostcycle(graph<S> &G){int n = G.get_vnum();const S SINF = numeric_limits<S>::max()/2;S cost = SINF;edges<S> min_cyc;for(int s=0; s<n; s++){auto cyc = find_mincostcycle(G, s);if(cyc.empty()) continue;S sum = 0;for(auto e : cyc) sum += e.cost;if(sum < cost){cost = sum;min_cyc = cyc;}}return min_cyc;}template<typename T>static edges<T> find_minmeancycle(graph<T> &G){}template<typename T>static edges<T> enumerate_3cycle(graph<T> &G){}template<typename T>static edges<T> enumerate_4cycle(graph<T> &G){}};void solve(){int dir; cin >> dir;int n, m; cin >> n >> m;graph<ll> G(n, dir);for(int i=0; i<m; i++){int u, v; cin >> u >> v;u--; v--;ll w; cin >> w;G.add_edge(u, v, w);}auto cycle = cycle::find_mincostcycle<ll>(G);if(cycle.empty()){cout << -1 << '\n';return;}ll ans = 0;for(auto e : cycle) ans += e.cost;cout << ans << '\n';}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int T=1;//cin >> T;while(T--) solve();}