結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー |
|
提出日時 | 2024-06-09 13:27:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,451 ms / 2,000 ms |
コード長 | 6,799 bytes |
コンパイル時間 | 2,995 ms |
コンパイル使用メモリ | 200,712 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 02:30:50 |
合計ジャッジ時間 | 17,478 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
コンパイルメッセージ
main.cpp: In lambda function: main.cpp:108:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 108 | auto [tmp, v] = pq.top(); | ^ main.cpp: In function 'std::tuple<T, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> > > mincostcycle(graph<T>)': main.cpp:219:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 219 | auto [r_cost, r_vcycle, r_ecycle] = mincostcycle<T>(g, r); | ^ main.cpp: In function 'void solve()': main.cpp:242:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 242 | auto [cost, vcycle, ecycle] = mincostcycle(g); | ^ main.cpp: In function 'std::tuple<T, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> > > mincostcycle(graph<T>, int) [with T = long long int]': main.cpp:207:1: warning: control reaches end of non-void function [-Wreturn-type] 207 | } | ^
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using pll = pair<ll, ll>;#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)#define rep(i, n) drep(i, 0, n - 1)#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) - 1;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>struct graph : std::vector<edges<T>>{int n = 0;int m = 0;edges<T> es;bool directed;graph(int n, bool directed) : n(n), directed(directed){(*this).resize(n);}void add_edge(int from, int to, T cost=1){if(directed){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++));}}};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>tuple<T, vector<int>, vector<int>> mincostcycle(graph<T> g, int s){struct dat{T dist;int pv;int pe;};int n = g.n;const T TINF = numeric_limits<T>::max()/2;bool is_directed = g.directed;// return shortest path tree vec, vec[v] = {dist(r, v), parent of r, edge id of (parent of r, r)};function<vector<dat>()> dijkstra = [&](){vector<dat> vec(n, {TINF, -1, -1});vec[s].dist = 0;priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;pq.push({0, s});while(!pq.empty()){auto [tmp, v] = pq.top();pq.pop();if(vec[v].dist < tmp) continue;for(edge<T> e : g[v]){if(vec[v].dist+e.cost < vec[e.to].dist){vec[e.to].dist = vec[v].dist + e.cost;vec[e.to].pv = v;vec[e.to].pe = e.id;pq.push({vec[e.to].dist, e.to});}}}return vec;};// g is a directed graphif(is_directed){vector<dat> vec = dijkstra();T cost = TINF;int vlast = -1;int elast = -1;for(int v=0; v<n; v++) for(edge<T> e : g[v]) if(e.to == s){if(vec[v].dist + e.cost < cost){cost = vec[v].dist + e.cost;vlast = v;elast = e.id;}}if(cost == TINF) return {T(-1), {}, {}};vector<int> vcycle;vector<int> ecycle;ecycle.push_back(elast);while(vlast != -1){vcycle.push_back(vlast);ecycle.push_back(vec[vlast].pe);vlast = vec[vlast].pv;}ecycle.pop_back();reverse(all(vcycle));reverse(all(ecycle));return {cost, vcycle, ecycle};}// g is an undirected graphif(!is_directed){vector<dat> vec = dijkstra();graph<bool> spt(n, false);for(int v=0; v<n; v++) if(v!=s && vec[v].dist != TINF){spt.add_edge(v, vec[v].pv);}vector<int> label(n, -1);label[s] = s;function<void(int, int, int)> dfs = [&](int v, int p, int l){label[v] = l;for(edge<bool> e : spt[v]) if(e.to != p) dfs(e.to, v, l);};for(edge<bool> e : spt[s]) dfs(e.to, s, e.to);T cost = TINF;int x = -1, y = -1, min_e = -1;for(int v=0; v<n; v++) if(v != s) for(edge<T> e : g[v]){if(vec[v].pv != e.to && label[v] != label[e.to]){if(vec[v].dist + vec[e.to].dist + e.cost < cost){cost = vec[v].dist + vec[e.to].dist + e.cost;x = v;y = e.to;min_e = e.id;}}}if(cost == TINF) return {T(-1), {}, {}};vector<int> vcycle, ecycle;ecycle.push_back(min_e);while(x != -1){vcycle.push_back(x);ecycle.push_back(vec[x].pe);x = vec[x].pv;}ecycle.pop_back();reverse(all(vcycle));reverse(all(ecycle));while(y != s){vcycle.push_back(y);ecycle.push_back(vec[y].pe);y = vec[y].pv;}return {cost, vcycle, ecycle};}}template<typename T>tuple<T, vector<int>, vector<int>> mincostcycle(graph<T> g){int n = g.n;const T TINF = numeric_limits<T>::max()/2;T cost = TINF;vector<int> vcycle;vector<int> ecycle;for(int r=0; r<n; r++){auto [r_cost, r_vcycle, r_ecycle] = mincostcycle<T>(g, r);if(r_cost != -1 && r_cost < cost){cost = r_cost;vcycle = r_vcycle;ecycle = r_ecycle;}}if(cost == TINF) return {T(-1), {}, {}};else return {cost, vcycle, ecycle};}void solve(){bool type; cin >> type;int n, m; cin >> n >> m;graph<ll> g(n, type);for(int i=0; i<m; i++){int u, v; cin >> u >> v;ll w; cin >> w;u--; v--;g.add_edge(u, v, w);}auto [cost, vcycle, ecycle] = mincostcycle(g);cout << cost << '\n';}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int T=1;//cin >> T;while(T--) solve();}