結果
問題 | No.1320 Two Type Min Cost Cycle |
ユーザー | tonegawa |
提出日時 | 2024-12-14 08:04:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 38,823 bytes |
コンパイル時間 | 2,612 ms |
コンパイル使用メモリ | 201,552 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-14 08:04:39 |
合計ジャッジ時間 | 4,903 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#line 1 ".lib/template.hpp"#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>#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 T>std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){int sz = v.size();if(sz==0) 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==0) 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==0) 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>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>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;}void io_init(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);}#line 1 ".lib/graph/graph.hpp"#line 1 ".lib/graph/edge.hpp"/*template<typename edge_weight>struct edge_base{using weight = edge_weight;int to();int from();int id();weight wei();static weight z();edge_base<weight> reverse();};*/template<typename edge_weight>struct simple_edge{using weight = edge_weight;int s, t;simple_edge(): s(-1), t(-1){}simple_edge(int a, int b): s(a), t(b){}int to(){return t;}int from(){return s;}int id(){return -1;}weight wei(){return 1;}static weight z(){return 0;}simple_edge<weight> reverse(){return simple_edge<weight>{t, s};}};template<typename edge_weight>struct weighted_edge{using weight = edge_weight;int s, t;weight w;weighted_edge(): s(-1), t(-1), w(0){}weighted_edge(int a, int b, weight c): s(a), t(b), w(c){}int to(){return t;}int from(){return s;}int id(){return -1;}weight wei(){return w;}static weight z(){return 0;}weighted_edge<weight> reverse(){return weighted_edge<weight>{t, s, w};}};template<typename edge_weight>struct labeled_edge{using weight = edge_weight;int s, t, i;labeled_edge(): s(-1), t(-1), i(-1){}labeled_edge(int a, int b, int i): s(a), t(b), i(i){}int to(){return t;}int from(){return s;}int id(){return i;}weight wei(){return 1;}static weight z(){return 0;}labeled_edge<weight> reverse(){return labeled_edge<weight>{t, s, i};}};template<typename edge_weight>struct weighted_labeled_edge{using weight = edge_weight;int s, t;weight w;int i;weighted_labeled_edge(): s(-1), t(-1), i(-1), w(0){}weighted_labeled_edge(int a, int b, weight w, int i): s(a), t(b), w(w), i(i){}int to(){return t;}int from(){return s;}int id(){return i;}weight wei(){return w;}static weight z(){return 0;}weighted_labeled_edge<weight> reverse(){return weighted_labeled_edge<weight>{t, s, w, i};}};#line 1 ".lib/graph/graph_algorithm.hpp"#line 7 ".lib/graph/graph_algorithm.hpp"#include <limits>#line 9 ".lib/graph/graph_algorithm.hpp"namespace graph_algorithm{template<typename T>using vec = std::vector<T>;// O(V + E)// 辺の重みが1template<typename edge>struct bfs_shortest_path{private:using weight = typename edge::weight;using dist_p = std::pair<weight, int>;vec<vec<edge>> &g;public:bfs_shortest_path(vec<vec<edge>> &g): g(g){}static constexpr weight inf = std::numeric_limits<weight>::max() / 2;static constexpr weight minf = std::numeric_limits<weight>::min() / 2;vec<weight> dist;vec<edge> par;void build(int s){int n = g.size();if(dist.empty()){dist.resize(n, inf);par.resize(n, edge{});}else{std::fill(dist.begin(), dist.end(), inf);std::fill(par.begin(), par.end(), edge{});}std::queue<dist_p> que;dist[s] = edge::z();que.push(dist_p(edge::z(), s));while(!que.empty()){auto [w, v] = que.top();que.pop();if(dist[v] < w) continue;for(edge &e: g[v]){assert(e.wei() == 1);weight d = dist[v] + e.wei();int to = e.to();if(dist[to] > d){dist[to] = d;par[to] = e;que.push(dist_p(d, to));}}}}vec<edge> get_path(int v){assert(!dist.empty());vec<edge> ret;while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();std::reverse(ret.begin(), ret.end());return ret;}weight operator [](int v){return dist[v];}};// O(V + E)// 辺の重みが0か1template<typename edge>struct zero_one_bfs_shortest_path{private:using weight = typename edge::weight;using dist_p = std::pair<weight, int>;vec<vec<edge>> &g;public:zero_one_bfs_shortest_path(vec<vec<edge>> &g): g(g){}static constexpr weight inf = std::numeric_limits<weight>::max() / 2;static constexpr weight minf = std::numeric_limits<weight>::min() / 2;vec<weight> dist;vec<edge> par;void build(int s){int n = g.size();if(dist.empty()){dist.resize(n, inf);par.resize(n, edge{});}else{std::fill(dist.begin(), dist.end(), inf);std::fill(par.begin(), par.end(), edge{});}std::queue<dist_p> que0, que1;dist[s] = edge::z();que0.push(dist_p(edge::z(), s));while(!que0.empty() && !que1.empty()){if(que0.empty()){que0 = que1;que1.clear();}auto [w, v] = que0.top();que0.pop();if(dist[v] < w) continue;for(edge &e: g[v]){weight w = e.wei();assert(w == 0 || w == 1);weight d = dist[v] + w;int to = e.to();if(dist[to] > d){dist[to] = d;par[to] = e;if(w == 0) que0.push(dist_p(d, to));else que1.push(dist_p(d, to));}}}}vec<edge> get_path(int v){assert(!dist.empty());vec<edge> ret;while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();std::reverse(ret.begin(), ret.end());return ret;}weight operator [](int v){return dist[v];}};// O((V + E)logV)// 辺の重みが非負(負の閉路がなければ一応動く)template<typename edge>struct dijkstra{private:using weight = typename edge::weight;using dist_p = std::pair<weight, int>;vec<vec<edge>> &g;public:dijkstra(vec<vec<edge>> &g): g(g){}static constexpr weight inf = std::numeric_limits<weight>::max() / 2;static constexpr weight minf = std::numeric_limits<weight>::min() / 2;vec<weight> dist;vec<edge> par;void build(int s){int n = g.size();if(dist.empty()){dist.resize(n, inf);par.resize(n, edge{});}else{std::fill(dist.begin(), dist.end(), inf);std::fill(par.begin(), par.end(), edge{});}std::priority_queue<dist_p, vec<dist_p>, std::greater<dist_p>> que;dist[s] = edge::z();que.push(dist_p(edge::z(), s));while(!que.empty()){auto [w, v] = que.top();que.pop();if(dist[v] < w) continue;for(edge &e: g[v]){weight d = dist[v] + e.wei();int to = e.to();if(dist[to] > d){dist[to] = d;par[to] = e;que.push(dist_p(d, to));}}}}vec<edge> get_path(int v){assert(!dist.empty());vec<edge> ret;while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();std::reverse(ret.begin(), ret.end());return ret;}weight operator [](int v){return dist[v];}};// O(VE)// inf: 到達不可, minf: 負の閉路template<typename edge>struct bellman_ford{private:using weight = typename edge::weight;using dist_p = std::pair<weight, int>;vec<vec<edge>> &g;public:bellman_ford(vec<vec<edge>> &g): g(g){}static constexpr weight inf = std::numeric_limits<weight>::max() / 2;static constexpr weight minf = std::numeric_limits<weight>::min() / 2;vec<weight> dist;vec<edge> par;void build(int s){int n = g.size();if(dist.empty()){dist.resize(n, inf);par.resize(n);}else{std::fill(dist.begin(), dist.end(), inf);std::fill(par.begin(), par.end(), edge{});}dist[s] = edge::z();for(int lp = 0; ; lp++){bool update = false;for(int i = 0; i < n; i++){if(dist[i] == inf) continue;for(edge e : g[i]){weight &dto = dist[e.to()];if(dto == minf){if(dto != minf) update = true;dto = minf;}else if(dto == inf || dto > dist[i] + e.wei()){dto = (lp > n ? minf : dist[i] + e.wei());par[e.to()] = e;update = true;}}}if(!update) break;}}vec<edge> get_path(int v){assert(!dist.empty());vec<edge> ret;while(par[v].from() != -1) ret.push_back(par[v]), v = par[v].from();std::reverse(ret.begin(), ret.end());return ret;}weight operator [](int v){return dist[v];}};// O(V^3)template<typename edge>struct warshall_floyd{private:using weight = typename edge::weight;vec<vec<edge>> &g;public:warshall_floyd(vec<vec<edge>> &g): g(g){}static constexpr weight inf = std::numeric_limits<weight>::max() / 2;static constexpr weight minf = std::numeric_limits<weight>::min() / 2;vec<vec<weight>> dist;void build(){int n = g.size();dist.resize(n, vec<weight>(n, inf));for(int i = 0; i < n; i++){dist[i][i] = 0;for(edge &e : g[i]){dist[i][e.to()] = std::min(dist[i][e.to()], e.wei());}}for(int k = 0; k < n; k++){for(int s = 0; s < n; s++){for(int t = 0; t < n; t++){dist[s][t] = std::min(dist[s][t], dist[s][k] + dist[k][t]);}}}}vec<weight>& operator [](int v){return dist[v];}};};namespace graph_algorithm{// {連結成分, DAG}template<typename edge>std::pair<vec<int>, vec<vec<int>>> scc(vec<vec<edge>> &g){int n = g.size();vec<int> v(n), cmp(n, 0);vec<vec<int>> rg(n), V;auto scc_dfs = [&](auto &&scc_dfs, int cur, int &sz)->void{cmp[cur] = -1;for(edge &e : g[cur]){int to = e.to();rg[to].push_back(cur);if(cmp[to] == 0) scc_dfs(scc_dfs, to, sz);}v[sz++] = cur;};auto scc_rdfs = [&](auto &&scc_rdfs, int cur, const int k)->void{cmp[cur] = k;V[k].push_back(cur);for(int to : rg[cur]) if(cmp[to] == -1) scc_rdfs(scc_rdfs, to, k);};for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) scc_dfs(scc_dfs, i, j);for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){if(cmp[v[i]] == -1){V.push_back(vec<int>());scc_rdfs(scc_rdfs, v[i], j++);}}return {cmp, V};}// {連結成分, 森}template<typename edge>std::pair<vec<int>, vec<vec<int>>> two_edge_connected(vec<vec<edge>> &g){int n = g.size();vec<int> v(n), cmp(n, 0);vec<vec<int>> V;vec<vec<bool>> edge_used(n);auto tec_dfs = [&](auto &&tec_dfs, int cur, int &sz)->void{cmp[cur] = -1;for(int i = 0; i < g[cur].size(); i++){int to = g[cur][i].to();if(cmp[to] == 0) edge_used[cur][i] = true, tec_dfs(tec_dfs, to, sz);}v[sz++] = cur;};auto tec_rdfs = [&](auto &&tec_rdfs, int cur, const int k)->void{cmp[cur] = k;V[k].push_back(cur);for(int i = 0; i < g[cur].size(); i++){int to = g[cur][i].to();if(cmp[to] == -1 && !edge_used[cur][i]) tec_rdfs(tec_rdfs, to, k);}};for(int i = 0; i < n; i++) edge_used[i].resize(g[i].size(), 0);for(int i = 0, j = 0; i < n; i++) if(!cmp[i]) tec_dfs(tec_dfs, i, j);for(int i = (int)v.size() - 1, j = 0; i >= 0; i--){if(cmp[v[i]] == -1){V.push_back(vec<int>());tec_rdfs(tec_rdfs, v[i], j++);}}return {cmp, V};}// 二重頂点連結成分分解// {間接点フラグ, 各連結成分が含む頂点}template<typename edge>std::pair<vec<bool>, vec<vec<int>>> bcc(vec<vec<edge>> &g){int n = g.size();vec<vec<int>> V;vec<int> child(n, 0), dep(n, -1), low(n);vec<bool> used(n, false), is_articulation(n, false);vec<edge> tmp_edge;auto bcc_dfs = [&](auto &&bcc_dfs, int cur, int par, int d)->void{if(par != -1) child[par]++;dep[cur] = low[cur] = d;for(edge &e : g[cur]){int to = e.to();if(to == par) continue;if(dep[to] < dep[cur]) tmp_edge.push_back(e);if(dep[e.to()] == -1){bcc_dfs(bcc_dfs, to, cur, d + 1);if(low[to] >= dep[cur]){is_articulation[cur] = true;V.push_back(vec<int>());bool is_ok = false;while(!tmp_edge.empty() && !is_ok){edge e = tmp_edge.back();tmp_edge.pop_back();if(e.from() == cur && e.to() == to) is_ok = true;if(!used[e.to()]) V.back().push_back(e.to()), used[e.to()] = true;if(!used[e.from()]) V.back().push_back(e.from()), used[e.from()] = true;}for(int v : V.back()) used[v] = false;}low[cur] = std::min(low[cur], low[to]);}else low[cur] = std::min(low[cur], dep[to]);}};for(int i = 0; i < n; i++){if(dep[i] != -1) continue;int vsz_pre = V.size();bcc_dfs(bcc_dfs, i, -1, 0);is_articulation[i] = (child[i] > 1);if(V.size() == vsz_pre) V.push_back(vec<int>{i});// 孤立点}return {is_articulation, V};}template<typename edge>std::tuple<vec<bool>, vec<int>, vec<vec<simple_edge<int>>>> block_cut_tree(vec<vec<edge>> &g){auto [is_articulation, V] = bcc<edge>(g);int n = g.size();vec<int> cmp(n, -1);int m = V.size(), a = m;for(int i = 0; i < m; i++){for(int v : V[i]){if(is_articulation[v]) cmp[v] = a++;else cmp[v] = i;}}vec<vec<simple_edge<int>>> G(a);for(int i = 0; i < m; i++){for(int v : V[i]){if(is_articulation[v]){G[i].push_back({i, cmp[v]});G[cmp[v]].push_back({cmp[v], i});}}}return {is_articulation, cmp, G};}};namespace graph_algorithm{// 終了時にinが0でない要素がある -> 閉路が存在する// 閉路があるなら空のvectorを返すtemplate<typename edge>vec<int> topological_sort(vec<vec<edge>> &g){int n = g.size();std::queue<int> que;vec<int> in(n, 0), ret;for(int i = 0; i < n; i++) for(edge e : g[i]) in[e.to()]++;for(int i = 0; i < n; i++) if(!in[i]) que.push(i);while(!que.empty()){int p = que.front();que.pop();ret.push_back(p);for(edge &e : g[p]){int to = e.to();if(!(--in[to])) que.push(to);}}for(int i = 0; i < n; i++) if(in[i] != 0) return {};return ret;}// プリム法, 連結なら始点sは関係ないtemplate<typename edge>vec<edge> undirected_mst(vec<vec<edge>> &g, int s = 0){int n = g.size();assert(s < n);static vec<bool> V(n, 0);vec<edge> ret;using pde = std::pair<typename edge::weight, edge>;std::priority_queue<pde, vec<pde>, std::function<bool(pde, pde)>> que([](pde a, pde b){return a.first > b.first;});V[s] = true;for(edge &e : g[s]) que.push(pde{e.wei(), e});while(!que.empty()){auto [d, e] = que.top();que.pop();if(V[e.to()]) continue;V[e.to()] = true;ret.push_back(e);for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});}for(edge &e : ret) V[e.to()] = V[e.from()] = false;return ret;}// rを根とするbfs木O(V + E)template<typename edge>vec<vec<edge>> bfs_tree(vec<vec<edge>> &g, int r){int n = g.size();std::queue<int> que;vec<bool> used(n, false);que.push(r);vec<vec<edge>> ret(n);used[r] = true;while(!que.empty()){int v = que.front();que.pop();for(edge &e : g[v]){int to = e.to();if(used[to]) continue;used[to] = true;ret[v].push_back(e);que.push(to);}}return ret;}// rを根とするbfs木, 最短経路的 O((V + E)logV)// {木, 重みのテーブル}template<typename edge>std::pair<vec<vec<edge>>, vec<typename edge::weight>> bfs_tree_shortest(vec<vec<edge>> &g, int r){int n = g.size();using weight = typename edge::weight;using pdv = std::pair<weight, int>;static constexpr weight inf = std::numeric_limits<weight>::max() / 2;std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> que;vec<weight> dist(n, inf);dist[r] = edge::z();que.push({edge::z(), r});vec<vec<edge>> ret(n);while(!que.empty()){auto [d, v] = que.top();que.pop();if(dist[v] < d) continue;for(edge &e : g[v]){int to = e.to();weight nxtd = d + e.wei();if(dist[to] > nxtd){dist[to] = nxtd;ret[v].push_back(e);que.push({nxtd, to});}}}return {ret, dist};}// g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)template<typename edge>void cmp_edge_arrange(const vec<int> &cmp, vec<vec<edge>> &g){int n = g.size();for(int i = 0; i < n; i++){int m = g[i].size();int l = 0, r = m - 1;while(l < r){while(l < m && cmp[i] == cmp[g[i][l].to()]) l++;while(0 < r && cmp[i] == cmp[g[i][r].to()]) r--;if(l < r) std::swap(g[i][l], g[i][r]);}}}};#line 7 ".lib/graph/graph.hpp"template<typename edge>struct general_graph{using weight = typename edge::weight;template<typename T>using vec = std::vector<T>;using graph = vec<vec<edge>>;using simple_graph = general_graph<simple_edge<int>>;int n;graph g;general_graph(int n): n(n), g(n){}general_graph(const vec<vec<edge>> &G): n(G.size()), g(G){}void add_edge(int a, edge e){g[a].push_back(e);}graph_algorithm::bfs_shortest_path<edge> bfs_shortest_path(){return graph_algorithm::bfs_shortest_path<edge>(g);}graph_algorithm::zero_one_bfs_shortest_path<edge> zero_one_bfs_shortest_path(){return graph_algorithm::zero_one_bfs_shortest_path<edge>(g);}graph_algorithm::dijkstra<edge> dijkstra(){return graph_algorithm::dijkstra<edge>(g);}graph_algorithm::bellman_ford<edge> bellman_ford(){return graph_algorithm::bellman_ford<edge>(g);}graph_algorithm::warshall_floyd<edge> warshall_floyd(){return graph_algorithm::warshall_floyd<edge>(g);}static simple_graph make_simple_graph(const vec<vec<int>> &G){int n = G.size();vec<vec<simple_edge<int>>> G2(n);for(int i = 0; i < n; i++) for(int j : G[i]) G2[i].push_back(simple_edge<int>(i, j));return simple_graph(G2);}// {連結成分, グラフ} 有向サイクルstd::pair<vec<int>, simple_graph> scc(){vec<int> cmp = graph_algorithm::scc(g).first;int m = *std::max_element(cmp.begin(), cmp.end());vec<vec<int>> G(m);for(int i = 0; i < n; i++){for(auto &e : g[i]){if(cmp[i] != cmp[e.t]){G[cmp[i]].push_back(cmp[e.t]);}}}for(int i = 0; i < m; i++){std::sort(G[i].begin(), G[i].end());G[i].erase(std::unique(G[i].begin(), G[i].end()), G[i].end());}return {cmp, make_simple_graph(G)};}// {連結成分, グラフ} 1つの辺が消えても連結, 森か木になるstd::pair<vec<int>, vec<vec<edge>>> two_edge_connected(){vec<int> cmp = graph_algorithm::scc(g).first;int m = *std::max_element(cmp.begin(), cmp.end());vec<vec<int>> G(m);for(int i = 0; i < n; i++){for(auto &e : g[i]){if(cmp[i] != cmp[e.t]){G[cmp[i]].push_back(cmp[e.t]);}}}return {cmp, G};}// {関節点フラグ, 各連結成分が含む頂点(関節点は複数の連結成分に含まれる))} 1つの頂点が消えても連結std::pair<vec<bool>, vec<vec<int>>> bcc(){return graph_algorithm::bcc<edge>(g);}// {関節点フラグ, cmp, 森} 1つの頂点が消えても連結, 森か木になるstd::tuple<vec<bool>, vec<int>, vec<vec<edge>>> block_cut_tree(){return graph_algorithm::block_cut_tree<edge>(g);}// 閉路が存在するなら空のvectorvec<int> topological_sort(){return graph_algorithm::topological_sort(g);}// 最小全域木, グラフが連結ならsの値は関係ないvec<edge> undirected_mst(int s = 0){return graph_algorithm::undirected_mst<edge>(g, s);}// rを根とするbfs木O(V + E)vec<vec<edge>> bfs_tree(int r){return graph_algorithm::bfs_tree(g, r);}// rを根とするbfs木, rからの最短経路 O((V + E)logV)std::pair<vec<vec<edge>>, vec<weight>> bfs_tree_shortest(int r){return graph_algorithm::bfs_tree_shortest(g, r);}// g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)void cmp_edge_arrange(const vec<int> &cmp){graph_algorithm::cmp_edge_arrange(cmp, g);}vec<edge> &operator [](int i){return g[i];}};using simple_graph = general_graph<simple_edge<int>>;template<typename T>using weighted_graph = general_graph<weighted_edge<T>>;template<typename T>using labeled_graph = general_graph<labeled_edge<T>>;template<typename T>using weighted_labeled_graph = general_graph<weighted_labeled_edge<T>>;#line 1 ".lib/graph/graph_algorithm_cycle.hpp"#line 6 ".lib/graph/graph_algorithm_cycle.hpp"#line 8 ".lib/graph/graph_algorithm_cycle.hpp"//#include "tree.hpp"//#include "../data_structure/segment_tree/dual_segment_tree.hpp"namespace graph_algorithm{template<typename T>using vec = std::vector<T>;// O(V + E)// ショートカットが無い閉路を1つ返す, 閉路が無い場合は空のvector// 自己辺はサイクルと見なさない(含めたい場合, e.from = e.toの辺を探す)// 多重辺があっても良い// 無向辺の場合辺にidをつけて逆流しないようにするtemplate<typename edge>void cycle_noshortcut(int cur, vec<vec<edge>> &g, vec<bool> &use, vec<int> &in, vec<edge> &E, vec<edge> &res, int last_edge_id){if(in[cur] >= 0){int s = 0;while(E[s].from() != cur) s++;// cur->curの閉路std::queue<edge> shortcut;std::fill(use.begin(), use.end(), 0);while(res.empty()){use[cur] = true;int skip_in = -1, end_in = -1;edge skip_e = g[cur][0], end_e = g[cur][0];for(edge &e : g[cur]){int to = e.to();if(in[to] == -1 || (last_edge_id == e.id())) continue;if(in[to] > in[cur] && skip_in < in[to]) skip_in = in[to], skip_e = e;if(in[to] < in[cur] && use[to] && end_in < in[to]) end_in = in[to], end_e = e;}if(end_in != -1){int to = end_e.to();while(E[s].from() != to) s++;while(E.back().to() != cur) E.pop_back();while(!shortcut.empty() && in[shortcut.front().to()] <= in[to]) shortcut.pop();E.push_back(end_e);while(s != E.size()){int srank = (shortcut.empty() ? g.size() : in[shortcut.front().from()]);while(s != E.size() && in[E[s].from()] < srank) res.push_back(E[s++]);if(!shortcut.empty()){int trank = in[shortcut.front().to()];res.push_back(shortcut.front());shortcut.pop();while(in[E[s].from()] < trank) s++;}}return;}if(in[cur] + 1 != skip_in) shortcut.push(skip_e);cur = skip_e.to();last_edge_id = skip_e.id();}return;}in[cur] = E.size();for(edge &e : g[cur]){if(e.to() == cur) continue;if(!use[e.to()] && res.empty() && (e.id() == -1 || e.id() != last_edge_id)){E.push_back(e);cycle_noshortcut<edge>(e.to(), g, use, in, E, res, e.id());E.pop_back();}}use[cur] = true;in[cur] = -1;}// accept_self_loop := trueなら自己辺も長さ1のサイクルとみなすtemplate<typename edge>vec<edge> cycle_noshortcut(vec<vec<edge>> &g, bool accept_self_loop){int n = g.size();if(accept_self_loop){for(int i = 0; i < n; i++){for(auto &e : g[i]){if(e.to() == e.from()){return {e}; // 自己辺をサイクルと見なすか}}}}vec<bool> use(n, false);vec<int> in(n, -1);vec<edge> res, E;for(int i = 0; i < n; i++){if(use[i]) continue;cycle_noshortcut<edge>(i, g, use, in, E, res, -1);if(!res.empty()) break;}return res;}// 全体の最小コスト閉路// O(V(V + E)logV)template<typename edge>std::pair<typename edge::weight, vec<edge>> cycle_mincost(const vec<vec<edge>> &g, bool directed, bool accept_self_loop){using weight = typename edge::weight;using pdv = std::pair<weight, int>;static constexpr weight inf = std::numeric_limits<weight>::max() / 2;auto chmin = [&](weight &a, weight b)->bool{if(a > b){a = b;return true;}return false;};int n = g.size();std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> que;vec<vec<edge>> cpg = g;for(int v = 0; v < n; v++) std::sort(cpg[v].begin(), cpg[v].end(), [](edge &a, edge &b){return a.to() < b.to();});weight ans = inf;vec<edge> E;for(int v = n - 1; v >= 0; v--){vec<weight> dist(v + 1, inf);dist[v] = edge::z();que.push({edge::z(), v});vec<edge> par(v), unused;while(!que.empty()){auto [d, u] = que.top();que.pop();if(dist[u] < d) continue;for(int i = 0; i < cpg[u].size(); i++){int to = cpg[u][i].to();if(to > v){cpg[u].pop_back();continue;}weight nxtd = d + cpg[u][i].wei();if(chmin(dist[to], nxtd)){par[to] = cpg[u][i];que.push({nxtd, to});}else if(par[u].id() != cpg[u][i].id()) unused.push_back(cpg[u][i]);}}weight pre_ans = ans;edge tmp_edge;if(!directed){for(edge &e : unused){if(dist[e.from()] == inf || dist[e.to()] == inf) continue;if(e.from() == e.to()){if(accept_self_loop && e.to() == v && chmin(ans, e.wei())){tmp_edge = e; // 自己辺をサイクルとみなす場合}continue;}if(chmin(ans, e.wei() + dist[e.from()] + dist[e.to()])) tmp_edge = e;}}else{for(edge &e : unused){if(dist[e.from()] == inf) continue;if(accept_self_loop && e.to() == v && chmin(ans, e.wei() + dist[e.from()])){tmp_edge = e; // 自己辺をサイクルとみなす場合}if(e.from() != v && e.to() == v && chmin(ans, e.wei() + dist[e.from()])) tmp_edge = e;}}if(ans < pre_ans){E.clear();int a = tmp_edge.from();while(a != v){E.push_back(par[a]);a = par[a].from();}std::reverse(E.begin(), E.end());E.push_back(tmp_edge);a = tmp_edge.to();while(a != v){E.push_back(par[a].reverse());a = par[a].from();}}}return {ans, E};}// 全体の最小コスト閉路// O(V(V + E)logV)template<typename edge>std::pair<typename edge::weight, vec<edge>> cycle_mincost2(const vec<vec<edge>> &g, bool directed, bool weighted, bool accept_self_loop){using weight = typename edge::weight;using pdv = std::pair<weight, int>;static constexpr weight inf = std::numeric_limits<weight>::max() / 2;auto chmin = [&](weight &a, weight b)->bool{if(a > b){a = b;return true;}return false;};int n = g.size();vec<vec<edge>> cpg = g;for(int v = 0; v < n; v++) std::sort(cpg[v].begin(), cpg[v].end(), [](edge &a, edge &b){return a.to() < b.to();});std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> q1;std::queue<pdv> q2;std::function<pdv()> get_top = [&]()->pdv{pdv ret = q1.top();q1.pop();return ret;};std::function<void(pdv)> push = [&](pdv a)->void{q1.push(a);};std::function<bool()> empty = [&]()->bool{return q1.empty();};if(!weighted){get_top = [&]()->pdv{pdv ret = q2.front();q2.pop();return ret;};push = [&](pdv a)->void{q2.push(a);};empty = [&]()->bool{return q2.empty();};}weight ans = inf;vec<edge> E;for(int v = n - 1; v >= 0; v--){vec<weight> dist(v + 1, inf);dist[v] = edge::z();push({edge::z(), v});vec<edge> par(v), unused;while(!empty()){auto [d, u] = get_top();if(dist[u] < d) continue;for(int i = 0; i < cpg[u].size(); i++){int to = cpg[u][i].to();if(to > v){cpg[u].pop_back();continue;}weight nxtd = d + cpg[u][i].wei();if(chmin(dist[to], nxtd)){par[to] = cpg[u][i];push({nxtd, to});}else if(par[u].id() != cpg[u][i].id()) unused.push_back(cpg[u][i]);}}weight pre_ans = ans;edge tmp_edge;if(!directed){for(edge &e : unused){if(dist[e.from()] == inf || dist[e.to()] == inf) continue;if(e.from() == e.to()){if(accept_self_loop && e.to() == v && chmin(ans, e.wei())){tmp_edge = e; // 自己辺をサイクルとみなす場合}continue;}if(chmin(ans, e.wei() + dist[e.from()] + dist[e.to()])) tmp_edge = e;}}else{for(edge &e : unused){if(dist[e.from()] == inf) continue;if(accept_self_loop && e.to() == v && chmin(ans, e.wei() + dist[e.from()])){tmp_edge = e; // 自己辺をサイクルとみなす場合}if(e.from() != v && e.to() == v && chmin(ans, e.wei() + dist[e.from()])) tmp_edge = e;}}if(ans < pre_ans){E.clear();int a = tmp_edge.from();while(a != v){E.push_back(par[a]);a = par[a].from();}std::reverse(E.begin(), E.end());E.push_back(tmp_edge);a = tmp_edge.to();while(a != v){E.push_back(par[a].reverse());a = par[a].from();}}}return {ans, E};}// vを含む最小コストの閉路// O((V + E)logV)// 辺の重みが全て1の場合 O(V + E)template<typename edge>std::pair<typename edge::weight, vec<edge>> cycle_mincost_specific_vertex(vec<vec<edge>> &g, int v, bool directed, bool weighted, boolaccept_self_loop){using weight = typename edge::weight;using pdv = std::pair<weight, int>;static constexpr weight inf = std::numeric_limits<weight>::max() / 2;auto chmin = [&](weight &a, weight b)->bool{if(a > b){a = b;return true;}return false;};int n = g.size();std::priority_queue<pdv, vec<pdv>, std::greater<pdv>> q1;std::queue<pdv> q2;std::function<pdv()> get_top = [&]()->pdv{pdv ret = q1.top();q1.pop();return ret;};std::function<void(pdv)> push = [&](pdv a)->void{q1.push(a);};std::function<bool()> empty = [&]()->bool{return q1.empty();};if(!weighted){get_top = [&]()->pdv{pdv ret = q2.front();q2.pop();return ret;};push = [&](pdv a)->void{q2.push(a);};empty = [&]()->bool{return q2.empty();};}weight ans = inf;vec<edge> E;vec<weight> dist(n, inf);dist[v] = edge::z();push({edge::z(), v});vec<edge> par(n), unused;// 無向辺の場合lca(from, to)がvであることがvを含むサイクルになる必要十分条件// d1_ancestor[i] := iから辿ってどの深さ1のノードに辿り着くかvec<int> d1_ancestor(n, -1);while(!empty()){auto [d, u] = get_top();if(dist[u] < d) continue;if(par[u].from() == v) d1_ancestor[u] = u;else d1_ancestor[u] = d1_ancestor[par[u].from()];for(int i = 0; i < g[u].size(); i++){int to = g[u][i].to();weight nxtd = d + g[u][i].wei();if(chmin(dist[to], nxtd)){par[to] = g[u][i];push({nxtd, to});}else if(par[u].id() != g[u][i].id()) unused.push_back(g[u][i]); //無向辺の逆流対策}}edge tmp_edge;if(!directed){for(edge &e : unused){if(dist[e.from()] == inf || dist[e.to()] == inf) continue;if(e.from() == e.to()){if(accept_self_loop && e.to() == v && chmin(ans, e.wei())){tmp_edge = e; // 自己辺をサイクルと見なす場合}continue;}if(d1_ancestor[e.from()] == d1_ancestor[e.to()]) continue;if(chmin(ans, e.wei() + dist[e.from()] + dist[e.to()])) tmp_edge = e;}}else{for(edge &e : unused){if(dist[e.from()] == inf) continue;if(accept_self_loop && e.to() == v && chmin(ans, e.wei() + dist[e.from()])){tmp_edge = e; // 自己辺をサイクルと見なす場合}if(e.from() != v && e.to() == v && chmin(ans, e.wei() + dist[e.from()])) tmp_edge = e;}}if(ans != inf){int a = tmp_edge.from();while(a != v){E.push_back(par[a]);a = par[a].from();}std::reverse(E.begin(), E.end());E.push_back(tmp_edge);a = tmp_edge.to();while(a != v){E.push_back(par[a].reverse());a = par[a].from();}}return {ans, E};}/*// ! グラフが連結でない場合// res[i] := iを含む閉路 O(V^2 + Elog^2V)// 全ての辺に[0, E)のuniqueな値を振っておくtemplate<typename edge>vec<vec<edge>> undirected_cycle_detection_vv(vec<vec<edge>> &g){int n = g.size();tree<edge> t = bfs_tree<edge>(g, 0);vec<bool> used_edge{0};for(int i = 0; i < n; i++){for(edge &e : t.g[i]){assert(0 <= e.id() && e.id() <= 1e7);while(used_edge.size() <= e.id()) used_edge.resize(used_edge.size() << 1);used_edge[e.id()] = true;}}t.hld_build();t.bfs_build();dual_segment_tree<range_set_get_any, edge*, edge*> seg(n, nullptr);for(int i = 0; i < n; i++){for(edge &e : g[i]){if(e.id() >= used_edge.size() || !used_edge[e.id()]){// bfs木に含まれないfor(auto [l, r] : t.hld_p->unordered_path(e.from(), e.to())) seg.update(l, r, &e);if(e.id() < used_edge.size()) used_edge[e.id()] = true;}}}vec<vec<edge>> res(n);for(int i = 0; i < n; i++){if(!res[i].empty()) continue;edge *e = seg.get(t.hld_p->index_vertex(i));if(!e) continue;// iを含む閉路が無いvec<edge> E;int a = e->from(), b = e->to(), l = t.hld_p->lca(a, b);while(a != l){E.push_back(t.bfs_p->get_parent_edge(a));a = t.parent[a];}std::reverse(E.begin(), E.end());E.push_back(*e);while(b != l){E.push_back(t.bfs_p->get_parent_edge(b).reverse());b = t.parent[b];}for(edge &e : E) if(res[e.from()].empty()) res[e.from()] = E;}return res;}*/};#line 4 "a.cpp"int main(){io_init();int t;std::cin >> t;int n, m;std::cin >> n >> m;weighted_labeled_graph<ll> g(n);range(i, 0, m){int a, b, c;std::cin >> a >> b >> c;a--, b--;g.add_edge(a, {a, b, c, i});if(!t) g.add_edge(b, {b, a, c, i});}auto [ans, E] = graph_algorithm::cycle_mincost2<weighted_labeled_edge<ll>>(g.g, t, 1, 1);static constexpr ll inf = std::numeric_limits<ll>::max() / 2;std::cout << (ans == inf ? -1 : ans) << '\n';//for(auto &e : E) std::cout << e.from() << " " << e.to() << " " << e.wei() << '\n';}