結果
問題 |
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 second mt19937_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){ // initilization n = G.get_vnum(); dist.resize(n, TINF); vpar.resize(n, -1); epar.resize(n); // running Dijkstra algorithm run(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 graph if(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 graph if(!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(); }