結果
| 問題 | No.1320 Two Type Min Cost Cycle |
| ユーザー |
 tonegawa
|
| 提出日時 | 2023-05-04 16:50:24 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 34,438 bytes |
| コンパイル時間 | 2,097 ms |
| コンパイル使用メモリ | 162,528 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-05-02 00:21:44 |
| 合計ジャッジ時間 | 16,937 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | WA | - |
| testcase_02 | AC | 2 ms
6,944 KB |
| testcase_03 | AC | 1 ms
6,944 KB |
| testcase_04 | WA | - |
| testcase_05 | AC | 4 ms
6,940 KB |
| testcase_06 | WA | - |
| testcase_07 | OLE | - |
| testcase_08 | AC | 51 ms
6,944 KB |
| testcase_09 | AC | 642 ms
6,944 KB |
| testcase_10 | OLE | - |
| testcase_11 | AC | 496 ms
6,940 KB |
| testcase_12 | AC | 122 ms
6,944 KB |
| testcase_13 | AC | 273 ms
6,944 KB |
| testcase_14 | AC | 43 ms
6,944 KB |
| testcase_15 | OLE | - |
| testcase_16 | AC | 4 ms
5,376 KB |
| testcase_17 | OLE | - |
| testcase_18 | OLE | - |
| testcase_19 | OLE | - |
| testcase_20 | AC | 14 ms
5,376 KB |
| testcase_21 | AC | 333 ms
5,376 KB |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | AC | 2 ms
5,376 KB |
| testcase_28 | AC | 37 ms
5,376 KB |
| testcase_29 | OLE | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | AC | 576 ms
5,376 KB |
| testcase_34 | AC | 269 ms
5,376 KB |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | AC | 2 ms
5,376 KB |
| testcase_38 | AC | 3 ms
5,376 KB |
| testcase_39 | AC | 2 ms
5,376 KB |
| testcase_40 | AC | 2 ms
5,376 KB |
| testcase_41 | WA | - |
| testcase_42 | AC | 2 ms
5,376 KB |
| testcase_43 | OLE | - |
| testcase_44 | OLE | - |
| testcase_45 | AC | 966 ms
5,376 KB |
| testcase_46 | WA | - |
| testcase_47 | AC | 423 ms
5,376 KB |
| testcase_48 | OLE | - |
| testcase_49 | WA | - |
| testcase_50 | AC | 2 ms
5,376 KB |
| testcase_51 | AC | 2 ms
5,376 KB |
| testcase_52 | AC | 71 ms
5,376 KB |
| testcase_53 | AC | 38 ms
5,376 KB |
| testcase_54 | OLE | - |
| testcase_55 | OLE | - |
| testcase_56 | OLE | - |
| testcase_57 | AC | 446 ms
5,376 KB |
| testcase_58 | AC | 440 ms
5,376 KB |
| testcase_59 | AC | 437 ms
5,376 KB |
ソースコード
#line 2 ".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 all(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>;
template<typename T>
using vec = std::vector<T>;
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<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<sz;i++) v[i] = read_vec<T>(tail...);
return v;
}
void io_init(){
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
#line 2 ".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: edge_base<edge_weight>{
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: edge_base<edge_weight>{
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: edge_base<edge_weight>{
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: edge_base<edge_weight>{
using weight = edge_weight;
int s, t, i;
weight w;
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, i};}
};
#line 3 ".lib/graph/tree_algorithm.hpp"
// !
template<typename edge>
void tree_diameter_dfs(int cur, int par, typename edge::weight d, typename edge::weight &dmax, int &vmax, const vec<vec<edge>> &g){
if(d > dmax) dmax = d, vmax = cur;
for(edge &e : g[cur]){
if(e.to() == par) continue;
tree_diameter_dfs(e.to(), cur, d + e.wei(), dmax, vmax);
}
}
// {直径, s, t}
template<typename edge>
std::tuple<typename edge::weight, int, int> tree_diameter(const vec<vec<edge>> &g){
int s = 0, t = 0;
typename edge::weight d = edge::z();
tree_diameter_dfs(s, -1, 0, d, t, g);
s = t, t = 0, d = edge::z();
tree_diameter_dfs(s, -1, 0, d, t, g);
return {d, s, t};
}
template<typename edge>
std::tuple<vec<vec<int>>, vec<int>, vec<int>, vec<int>> centroid_decomposition_build(const vec<vec<edge>> &g){
int n = g.size();
assert(n);
vec<vec<int>> G(n);
std::vector<int> size_i(n, 0), dep_i(n, std::numeric_limits<int>::max()), par_i(n, -1);
auto add_edge = [&](int p, int c)->void{
G[p].push_back(c);
G[c].push_back(p);
par_i[c] = p;
};
auto find_centroid = [&](auto &&find_centroid, int v, int p, const int N, const int8_t rank)->std::pair<int, int>{
int sz = 1;
for(edge &e: g[v]){
if(e.t == p || dep_i[e.t] < rank) continue;
auto [sz_c, cent_c] = find_centroid(find_centroid, e.t, v, N, rank);
if(sz_c == -1) return {-1, cent_c};
size_i[e.t] = sz_c, sz += sz_c;
}
//サイズが半分以上になったとき
if(sz * 2 >= N){
size_i[v] = N;
dep_i[v] = rank;
for(edge &e: g[v]){
if(e.t == p || dep_i[e.t] < rank) continue;
auto [sz_c, cent_c] = find_centroid(find_centroid, e.t, -1, size_i[e.t], rank + 1);
assert(sz_c == -1);
add_edge(v, cent_c);
}
if(p != -1){
auto [sz_c, cent_c] = find_centroid(find_centroid, p, -1, N - sz, rank + 1);
assert(sz_c == -1);
add_edge(v, cent_c);
}
return {-1, v};// 重心を発見
}
return {sz, -1};
};
find_centroid(find_centroid, 0, -1, n, 0);
return {G, size_i, dep_i, par_i};
}
template<typename edge>
struct hld{
vec<int> subsize, depth, parent, in, out, head, rev;
hld(vec<vec<edge>> &g, int root){
build(g, root);
}
void dfs_sz(int cur, int par, int dep, vec<vec<edge>> &g){
depth[cur] = dep;
parent[cur] = par;
subsize[cur] = 1;
if(g[cur].size() && g[cur][0].to() == par) std::swap(g[cur][0], g[cur].back());
for(int i = 0; i < g[cur].size(); i++){
edge &e = g[cur][i];
if(e.to() == par) continue;
dfs_sz(e.to(), cur, dep + 1, g);
subsize[cur] += subsize[e.to()];
if(subsize[g[cur][0].to()] < subsize[e.to()]) std::swap(g[cur][0], e);
}
}
void dfs_hld(int cur, int par, int ×, vec<vec<edge>> &g){
in[cur] = times++;
rev[in[cur]] = cur;
for(edge &e : g[cur]){
if(e.to() == par) continue;
head[e.to()] = (g[cur][0].to() == e.to() ? head[cur] : e.to());
dfs_hld(e.to(), cur, times, g);
}
out[cur] = times;
}
void build(vec<vec<edge>> &g, int root){
int n = g.size();
subsize.resize(n), depth.resize(n), parent.resize(n);
in.resize(n), out.resize(n), head.resize(n), rev.resize(n);
dfs_sz(root, -1, 0, g);
int t = 0;
dfs_hld(root, -1, t, g);
}
int la(int v, int k){
if(depth[v] < k) return -1;
while(true){
int u = head[v];
if(in[v] - k >= in[u]) return rev[in[v] - k];
k -= in[v] - in[u] + 1;
v = parent[u];
}
}
int lca(int u, int v){
for(;; v = parent[head[v]]){
if(in[u] > in[v]) std::swap(u, v);
if(head[u] == head[v]) return u;
}
}
bool is_ancestor(int u, int v){
if(depth[u] > depth[v]) std::swap(u, v);
return u == la(v, depth[v] - depth[u]);
}
int kth_vertex_on_path(int u, int v, int k){
int l = lca(u, v), dlu = depth[u] - depth[l];
if(dlu > k) return la(u, k);
k = depth[v] - depth[l] - k + dlu;
if(k < 0) return -1;
return la(v, k);
}
// hldに基づいて頂点を[0, n), 辺を[1, n)に並び替えた時に, 任意のパスはO(log(n))個の区間になる
// 頂点[0, n)の中でuの位置
int index_vertex(int u){
return in[u];
}
// 辺[1, n)の中でe{s, t}の位置, 辺が存在しない場合は-1
int index_edge(int s, int t){
if(in[s] > in[t]) std::swap(s, t);
if(parent[t] != s) return -1;
return in[s] + 1;
}
using path = vec<std::pair<int, int>>;
// 順序を気にせずO(log(n))個の区間を列挙
path unordered_path(int u, int v, bool is_edge = false){
path res;
for(;; v = parent[head[v]]){
if(in[u] > in[v]) std::swap(u, v);
if(head[u] == head[v]) break;
res.push_back({in[head[v]], in[v] + 1});
}
res.push_back({in[u] + is_edge, in[v] + 1});
return res;
}
// {lca->uのパス, lca->vのパス}
std::pair<path, path> ordered_path(int u, int v, bool is_edge = false){
bool is_swaped = false;
std::pair<path, path> res;
path &a = res.first, &b = res.second;
for(;; v = parent[head[v]]){
if(in[u] > in[v]) std::swap(u, v), std::swap(a, b), is_swaped ^= 1;
if(head[u] == head[v]) break;
b.push_back({in[head[v]], in[v] + 1});
}
b.push_back({in[u] + is_edge, in[v] + 1});
if(is_swaped) std::swap(a, b);
std::reverse(a.begin(), a.end());
std::reverse(b.begin(), b.end());
return {a, b};
}
};
// !
// 部分木のサイズ, 深さ, 親
template<typename edge>
std::tuple<vec<int>, vec<int>, vec<int>> simple_dfs(const vec<vec<edge>> &g, int root){
int n = g.size();
vec<int> sz(n, 1), de(n), pa(n);
auto simple_dfs_f = [&](auto simple_dfs_f, int cur, int par, int dep)->void{
pa[cur] = par;
de[cur] = dep;
for(edge &e : g[cur]){
if(e.to() == par) continue;
simple_dfs_f(simple_dfs_f, e.to(), cur, dep + 1);
sz[cur] += sz[e.to()];
}
};
simple_dfs_f(simple_dfs_f, root, -1, 0);
return {sz, de, pa};
}
// !
// pre_order 頂点を初めて訪れた時刻を記録
// in_pre: 初めて訪れた時刻
// out_pre: in_pre以降に初めてvより上のノードが現れる時刻, 区間[in_pre, out_pre)は部分木
// rev_pre: in_preの順番に頂点を並び替えた状態
template<typename edge>
struct dfs_order{
vec<int> subsize, depth, parent;
vec<int> in_pre, out_pre, rev_pre;// 訪れた順番(サイズN)
vec<int> in_path, out_path, rev_path;// 戻る辺も考慮する(サイズ2N-1)
dfs_order(vec<vec<edge>> &g, int root){
build(g, root);
}
void dfs_build_inner(int cur, int par, int dep, int &tpath, int &tpre, vec<vec<edge>> &g){
depth[cur] = dep;
parent[cur] = par;
in_path[cur] = tpath;
rev_path[tpath++] = cur;
in_pre[cur] = out_path[cur] = tpre;
rev_pre[tpre++] = cur;
for(int i = 0; i < g[cur].size(); i++){
int to = g[cur][i].to();
if(to == par) continue;
dfs_build_inner(to, cur, dep + 1, tpath, tpre, g);
subsize[cur] += subsize[to];
out_path[cur] = tpath;
rev_path[tpath++] = cur;
}
out_pre[cur] = tpre;
}
void build(vec<vec<edge>> &g, int root){
int n = g.size();
depth.resize(n), parent.resize(n), subsize.resize(n, 1);
in_pre.resize(n), out_pre.resize(n), rev_pre.resize(n);
in_path.resize(n), out_path.resize(n), rev_path.resize(2 * n - 1);
int a = 0, b = 0;
dfs_build_inner(root, -1, 0, a, b, g);
}
// vがuの部分木に含まれるか(u自身も部分木)
bool is_subtree(int u, int v){
return in_path[u] <= in_path[v] && out_path[v] <= out_path[u];
}
// u->vパス(最短経路)にwが含まれるか(端点も含む)
// vがuの部分木 -> wがuの部分木 && vがwの部分木
// それ以外 -> wがuかvのどちらかを部分木として含む
bool is_contained_path(int u, int v, int w){
if(in_path[u] > in_path[v]) std::swap(u, v);
if(is_subtree(u, v)) return in_path[u] <= in_path[w] && is_subtree(w, v);
return is_subtree(w, u) || is_subtree(w, v);
}
// [in_pre, out_pre)がuの部分木中に存在する頂点番号
std::pair<int, int> subtree(int u){
return {in_pre[u], out_pre[u]};
}
/*
std::pair<int, int> path(){
}
*/
};
// !
template<typename edge>
struct bfs_order{
vec<int> parent;
vec<int> in_bfs, rev_bfs, child_in;
vec<vec<edge>> &g;
bfs_order(vec<vec<edge>> &g, int root):g(g){
build(root);
}
// 注: g[v][親]が末尾にswapされる
void build(int root){
int n = g.size();
in_bfs.resize(n);
rev_bfs.resize(n);
child_in.resize(n, -1);
parent.resize(n);
std::queue<std::pair<int, int>> q;
q.push({root, -1});
int t = 0;
while(!q.empty()){
auto [v, p] = q.front();
q.pop();
parent[v] = p;
if(child_in[p] == -1) child_in[p] = t;
rev_bfs[t] = v;
in_bfs[v] = t++;
for(int i = 0; i < g[v].size(); i++){
if(g[v][i].to() == p) std::swap(g[v][i], g[v].back());
q.push({g[v][i].to(), v});
}
}
}
// vがuの何番目の子か(0-indexed), 親でない場合-1
int child_index_find(int u, int v){
if(parent[v] != u) return -1;
return in_bfs[v] - child_in[u];
}
// e{u, v}を探す
edge get_edge(int u, int v){
return g[u][child_index_find(u, v)];
}
edge get_parent_edge(int u){
/*
// 辺が親->子片方向だと壊れる
return g[u].back();
*/
int p = parent[u];
return g[p][child_index_find(p, u)];
}
};
template<int (*lca)(int, int), int (*dfs_in)(int), int (*dep)(int)>
std::pair<vec<int>, vec<std::pair<int, int>>> lca_tree_build(vec<int> v){
if(v.empty()) return {};
std::sort(v.begin(), v.end(), [&](int a, int b){return dfs_in(a) < dfs_in(b);});
v.erase(std::unique(v.begin(), v.end()), v.end());
std::stack<int> st;
vec<std::pair<int, int>> E;
vec<int> V;
st.push(v[0]);
for(int i = 1; i < v.size(); i++){
if(v[i] == v[i - 1]) continue;
int l = lca(v[i], v[i - 1]);
while(true){
int c = st.top();
st.pop();
if(st.empty() || dep(st.top()) <= dep(l)){
st.push(l);
st.push(v[i]);
if(dep(c) > dep(l)){
E.push_back({l, c});
V.push_back(c);
V.push_back(l);
}
break;
}
int p = st.top();
if(dep(c) > dep(p)){
E.push_back({p, c});
V.push_back(c), V.push_back(p);
}
}
}
while(st.size() >= 2){
int c = st.top();
st.pop();
int p = st.top();
if(c != p) E.push_back({p, c}), V.push_back(c), V.push_back(p);
}
if(!st.empty()) V.push_back(st.top());
std::sort(V.begin(), V.end());
V.erase(std::unique(V.begin(), V.end()), V.end());
return {V, E};
}
#line 5 ".lib/graph/tree.hpp"
template<typename edge>
struct tree{
using weight = typename edge::weight;
template<typename T>
using vec = std::vector<T>;
using graph = vec<vec<edge>>;
using simple_tree = tree<simple_edge<int>>;
public:
graph g;
int n, r;
vec<int> subsize, depth, parent;
hld<edge> *hld_p;
dfs_order<edge> *dfs_p;
bfs_order<edge> *bfs_p;
tree(int n, int r = 0): g(n), n(n), r(r), hld_p(nullptr), dfs_p(nullptr), bfs_p(nullptr){}
tree(graph &g, int r = 0): g(g), n(g.size()), r(r), hld_p(nullptr), dfs_p(nullptr), bfs_p(nullptr){}
void add_edge(int a, edge e){
assert(0 <= a && a < n);
g[a].push_back(e);
}
void add_dual(int a, int b, edge e){
assert(0 <= a && a < n);
g[a].push_back(e);
g[b].push_back(e.reverse());
}
void simple_dfs(){
auto [s, d, p] = simple_dfs(g, r);
subsize = s, depth = d, parent = p;
}
void hld_build(){
hld_p = new hld<edge>(g, r);
subsize = hld_p->subsize, depth = hld_p->depth, parent = hld_p->parent;
}
void dfs_build(){
dfs_p = new dfs_order(g, r);
subsize = dfs_p->subsize, depth = dfs_p->depth, parent = dfs_p->parent;
}
void bfs_build(){
bfs_p = new bfs_order(g, r);
parent = bfs_p->parent;
}
int lca(int u, int v){
return hld_p->lca(u, v);
}
int la(int u, int k){
return hld_p->la(u, k);
}
int dep(int v){
return depth[v];
}
int par(int v){
return parent[v];
}
int size(int v){
return subsize[v];
}
std::pair<vec<int>, vec<std::pair<int, int>>> lca_tree(vec<int> v){
static std::function<int(int, int)> dfs_in = [&](int v){return dfs_p->in_pre[v];};
return lca_tree_build<lca, dfs_in, dep>(v);
}
// vがuの何番目の子か(0-indexed), 親でない場合-1
int child_index_find(int u, int v){
return bfs_p->child_index_find(u, v);
}
// s->tパスの辺
vec<edge> get_path(int s, int t){
int l = lca(s, t);
vec<edge> L, R;
while(s != l){
L.push_back(g[s].back());
s = parent[s];
}
while(t != l){
int p = parent[l];
R.push_back(g[p][child_index_find(p, l)]);
l = p;
}
std::reverse(R.begin(), R.end());
L.insert(L.end(), R.begin(), R.end());
return L;
}
// vがuの部分木に含まれるか(u自身も部分木)
bool is_subtree(int u, int v){
return dfs_p->is_subtree(u, v);
}
// u->vパス(最短経路)にwが含まれるか(端点も含む)
// vがuの部分木 -> wがuの部分木 && vがwの部分木
// それ以外 -> wがuかvのどちらかを部分木として含む
bool is_contained_path(int u, int v, int w){
return dfs_p->is_contained_path(u, v, w);
}
simple_tree centroid_decomposition(){
auto [G, root, size_i, par_i, dep_i] = centroid_decomposition_build<edge>(g);
simple_tree res(G, root);
res.subsize = size_i;
res.parent = par_i;
res.depth = dep_i;
return res;
}
vec<edge> &operator [](int i){return g[i];}
};
using simple_tree = tree<simple_edge<int>>;
#line 5 ".lib/graph/graph_algorithm.hpp"
// i-bit目が1 -> 頂点iを使う
long long maximum_independent_set(const vec<long long> &g2, long long rem){
int n = g2.size();
if(rem == -1) rem = (1LL << n) - 1;
long long ret = 0;
int k = -1, m = -1;
while(true){
bool update = false;
for(int i = 0; i < n; i++){
if(!((rem >> i) & 1)) continue;
int s = __builtin_popcountll(rem & g2[i]); //次数
if(s > m) k = i, m = s;
if(s <= 1){
rem &= ~(g2[i] | (1LL << i));
ret |= (1LL << i), update = true;
}
}
if(!update) break;
k = -1, m = -1;
}
if(rem > 0){
rem &= ~(1LL << k);
long long p = maximum_independent_set(g2, rem); //kを使わない
long long q = maximum_independent_set(g2, rem & ~g2[k]); //kを使う
if(__builtin_popcountll(p) > __builtin_popcountll(q)) ret |= p;
else ret |= ((1LL << k) | q);
}
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> res;
using pde = 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;
res.push_back(e);
for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});
}
for(edge &e : res) V[e.to()] = V[e.from()] = false;
return res;
}
// !
// プリム法
template<typename edge>
vec<vec<edge>> undirected_mst_forest(vec<vec<edge>> &g){
int n = g.size();
static vec<bool> V(n, 0);
vec<vec<edge>> res;
using pde = 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;
});
for(int i = 0; i < n; i++){
if(V[i]) continue;
V[i] = true;
res.push_back(vec<edge>());
for(edge &e : g[i]) 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;
res.push_back(e);
for(edge &ec : g[e.to()]) if(!V[ec.to()]) que.push({ec.wei(), ec});
}
for(edge &e : res.back()) V[e.to()] = V[e.from()] = false;
}
return res;
}
// !
// 終了時にinが0でない要素がある -> 閉路が存在する
template<typename edge>
vec<int> topological_sort(vec<vec<edge>> &g){
int n = g.size();
std::queue<int> que;
vec<int> in(n, 0), res;
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();
res.push_back(p);
for(edge &e : g[p]){
int to = e.to();
if(!(--in[to])) que.push(to);
}
}
return res;
}
template<typename edge>
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>
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>
pair<vec<int>, 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 {child, V};
}
// !
// 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]);
}
}
}
// !
// rを根とするbfs木, 重みを気にしない O(V + E)
template<typename edge>
tree<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);
tree<edge> res(n, r);
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;
res.add_edge(v, e);
que.push(to);
}
}
return res;
}
// !
// rを根とするbfs木, 最短経路的 O((V + E)logV)
// {木, 重みのテーブル}
template<typename edge>
std::pair<tree<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});
tree<edge> res(n, r);
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;
res.add_edge(v, e);
que.push({nxtd, to});
}
}
}
return {res, dist};
}
// O((V + E)logV)
// 辺の重みが非負
template<typename edge>
struct dijkstra{
private:
using weight = typename edge::weight;
using dist_p = 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> res;
while(par[v].from() != -1) res.push_back(par[v]), v = par[v].from();
std::reverse(res.begin(), res.end());
return res;
}
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 = 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> res;
while(par[v].from() != -1) res.push_back(par[v]), v = par[v].from();
std::reverse(res.begin(), res.end());
return res;
}
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];}
};
#line 5 ".lib/graph/graph.hpp"
/*
template<typename edge = int, typename dist = int, typename edge_type = simple_edge<edge, dist>>
struct dense_graph{
};
*/
template<typename edge>
struct general_graph{
using weight = typename edge::weight;
template<typename T>
using vec = std::vector<T>;
using graph = vec<vec<edge>>;
int n;
graph g;
general_graph(int n): n(n), g(n){}
void add_edge(int a, edge e){
g[a].push_back(e);
}
// i-bit目が1 -> 頂点iを使う
long long maximum_independent_set(){
assert(n <= 62);
vec<long long> g2(n, 0);
for(int i = 0; i < n; i++) for(edge &e : g[i]) g2[i] |= (1LL << e.to());
return maximum_independent_set(g2, -1);
}
// !
vec<edge> undirected_mst_build(int s = 0){
return undirected_mst<edge>(g, s);
}
// 終了時にinが0でない要素がある -> 閉路が存在する
vec<int> topological_sort(){
return topological_sort(g);
}
pair<vec<int>, vec<vec<int>>> scc(){
return scc(g);
}
pair<vec<int>, vec<vec<int>>> two_edge_connected_build(){
return two_edge_connected<edge>(g);
}
pair<vec<int>, vec<vec<int>>> bcc_build(){
return bcc<edge>(g);
}
// g[i]の辺を{同じcmpへの辺, 異なるcmpへの辺}に並び替える, O(V + E)
void cmp_edge_arrange(const vec<int> &cmp){
cmp_edge_arrange(cmp, g);
}
// rを根とするbfs木, 重みを気にしない O(V + E)
tree<edge> bfs_tree(int r){
return bfs_tree(g, r);
}
// rを根とするbfs木, 最短経路的 O((V + E)logV)
tree<edge> bfs_tree_shortest(int r){
return bfs_tree_shortest(g, r);
}
dijkstra<edge> dijkstra_build(){
return dijkstra<edge>(g);
}
bellman_ford<edge> bellman_ford_build(){
return bellman_ford<edge>(g);
}
warshall_floyd<edge> warshall_floyd_build(){
return warshall_floyd<edge>(g);
}
// O(E)
// 任意のサイクル bfs木 -> e{s, t}を min(dep[s], dep[t])の昇順に確かめる
// iを含む任意のサイクル bfs木 -> e{s, t}s, tのいずれかがiの部分木かつlca(s, t)がiより上
//
/*
vec<edge> undirected_cycle(const vec<int> &cmp, int s = 0){
static vec<bool> order(n, -1);
vec<edge> res;
}
*/
};
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 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});
}
static constexpr ll inf = std::numeric_limits<ll>::max() / 2;
ll ans = inf;
range(i, 0, n){
auto [T, D] = bfs_tree_shortest(g.g, i);
vec<bool> used(m, false);
range(j, 0, n) for(auto &e : T.g[j]) used[e.id()] = true;
if(!t){
range(j, 0, n){
for(auto &e : g.g[j]){
if(used[e.id()] || D[e.from()] == inf || D[e.to()] == inf) continue;
if(e.from() == e.to()){
if(e.from() == i) ans = min(ans, e.wei());
continue;
}
ans = min(ans, e.wei() + D[e.from()] + D[e.to()]);
}
}
}else{
std::cout << D << '\n';
range(j, 0, n){
for(auto &e : g.g[j]){
if(used[e.id()] || D[e.from()] == inf) continue;
if(e.to() == i){
ans = min(ans, e.wei() + D[e.from()]);
}
}
}
}
}
std::cout << (ans == inf ? -1 : ans) << '\n';
}