結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー tonegawatonegawa
提出日時 2024-12-14 07:55:09
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 580 ms / 2,000 ms
コード長 16,240 bytes
コンパイル時間 3,389 ms
コンパイル使用メモリ 214,428 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-14 07:55:19
合計ジャッジ時間 9,383 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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>
#include <thread>
#include <chrono>
#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 A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
dest << std::get<0>(t) << ' ' << std::get<1>(t);
return dest;
}
template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
return dest;
}
template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
return dest;
}
template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
int sz = v.size();
if (!sz) 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) 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) 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>
std::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>
std::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;
}
template<typename T, size_t size>
auto make_array(T x) {
std::array<T, size> res;
res.fill(x);
return res;
}
template<typename T, size_t size, size_t size2, size_t... Tail>
auto make_array(T x) {
std::array<decltype(make_array<T, size2, Tail...>(x)), size> res;
res.fill(make_array<T, size2, Tail...>(x));
return res;
}
// x / y
ll ceil_div(ll x, ll y) {
assert(y > 0);
return (x + (x > 0 ? y - 1 : 0)) / y;
}
// x / y
ll floor_div(ll x, ll y) {
assert(y > 0);
return (x + (x > 0 ? 0 : -y + 1)) / y;
}
void io_init() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
template<typename _W>
struct edge_base {
using W = _W;
int t;
edge_base() {}
edge_base(int _t) : t(_t) {}
virtual int from() const {
assert(false);
}
int to() const {
return t;
}
virtual W weight() const {
assert(false);
}
virtual int id() const {
assert(false);
}
operator int() const {
return t;
}
};
struct simple_edge : edge_base<int> {
simple_edge() {}
simple_edge(int _t) : edge_base<int>(_t) {}
int weight() const override {
return 1;
}
int id() const override {
return -1;
}
};
struct labeled_edge : edge_base<int> {
int _s, _id;
labeled_edge() {}
labeled_edge(int _s, int _t, int _id) : edge_base<int>(_t), _s(_s), _id(_id) {}
int weight() const override {
return 1;
}
int from() const override {
return _s;
}
int id() const override {
return _id;
}
};
template<typename _W>
struct weighted_edge : edge_base<_W> {
using W = _W;
W w;
weighted_edge() {}
weighted_edge(int _t, _W _w) : edge_base<_W>(_t), w(_w) {}
W weight() const override {
return w;
}
int id() const override {
return -1;
}
};
template<typename _W>
struct weighted_labeled_edge : edge_base<_W> {
using W = _W;
W w;
int _s, _id;
weighted_labeled_edge() : _id(-1) {}
weighted_labeled_edge(int _s, int _t, _W _w, int _id) : edge_base<_W>(_t), w(_w), _s(_s), _id(_id) {}
int from() const override {
return _s;
}
W weight() const override {
return w;
}
int id() const override {
return _id;
}
};
template <class E>
struct csr {
std::vector<int> start;
std::vector<E> elist;
csr() {}
explicit csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
~csr() {}
int N() const {
return start.size() - 1;
}
int deg(int i) const {
return start[i + 1] - start[i];
}
int begin(int i) const {
return start[i];
}
int end(int i) const {
return start[i + 1];
}
E& operator [] (int i) { return elist[i]; }
};
//
// O(V(V + E)logV)
template<typename edge>
struct cycle_detection_mincost {
using W = typename edge::W;
static constexpr W inf = std::numeric_limits<W>::max() / 2;
private:
csr<edge> g;
std::pair<std::vector<W>, std::vector<edge>> bfs_tree(int s) {
int N = g.N();
std::vector<W> dist(N, inf);
std::vector<edge> par(N);
std::queue<int> q;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = g.begin(v); i < g.end(v); i++) {
int to = g[i];
if (dist[v] + 1 < dist[to]) {
dist[to] = dist[v] + 1;
par[to] = g[i];
q.push(to);
}
}
}
return {dist, par};
}
std::pair<std::vector<W>, std::vector<edge>> dijkstra_tree(int s) {
int N = g.N();
std::vector<W> dist(N, inf);
std::vector<edge> par(N);
using P = std::pair<W, int>;
std::priority_queue<P, std::vector<P>, std::greater<P>> q;
q.push({0, s});
dist[s] = 0;
while (!q.empty()) {
auto [d, v] = q.top();
q.pop();
if (dist[v] != d) continue;
for (int i = g.begin(v); i < g.end(v); i++) {
int to = g[i];
W nd = dist[v] + g[i].weight();
if (nd < dist[to]) {
dist[to] = nd;
par[to] = g[i];
q.push({nd, to});
}
}
}
return {dist, par};
}
public:
cycle_detection_mincost(const csr<edge> &_g) : g(_g) {}
// v
// s-tid
// O((V + E)logV)
// O(V + E)
std::pair<W, std::vector<edge>> find(int v, bool directed, bool weighted, bool accept_self_loop) {
int N = g.N();
W w = inf;
int eid = -1;
if (accept_self_loop) {
for (int j = g.begin(v); j < g.end(v); j++) {
if (g[j].to() == v && w < g[j].weight()) {
w = g[j].weight();
eid = j;
}
}
}
std::vector<W> dist;
std::vector<edge> par;
std::vector<int> semi_root;
if (weighted) {
std::tie(dist, par) = dijkstra_tree(v);
} else {
std::tie(dist, par) = bfs_tree(v);
}
if (directed) {
for (int i = 0; i < N; i++) {
if (i == v || dist[i] == inf || dist[i] > w) continue;
for (int j = g.begin(i); j < g.end(i); j++) {
if (g[j].to() == v && dist[i] + g[j].weight() < w) {
w = dist[i] + g[j].weight();
eid = j;
}
}
}
} else {
semi_root.resize(N, -1);
auto dfs = [&](auto &&dfs, int u, int p, int sr) -> void {
semi_root[u] = sr;
for (int i = g.begin(u); i < g.end(u); i++) {
int to = g[i];
if (to == v || to == p || to == u || dist[to] == inf) continue;
if (par[to].id() == g[i].id()) {
dfs(dfs, to, u, sr);
}
}
};
for (int i = 0; i < N; i++) {
if (i == v || dist[i] == inf) continue;
if (par[i].from() == v) dfs(dfs, i, v, i);
}
for (int i = 0; i < N; i++) {
if (i == v || dist[i] == inf || dist[i] > w) continue;
for (int j = g.begin(i); j < g.end(i); j++) {
int to = g[j];
if (g[j].id() == par[i].id()) continue;
if (semi_root[i] == semi_root[to]) continue;
if (dist[i] + dist[to] + g[j].weight() < w) {
w = dist[i] + dist[to] + g[j].weight();
eid = j;
}
}
}
}
if (w == inf) return {inf, {}};
std::vector<edge> res;
res.push_back(g[eid]);
int u = g[eid].from();
while (u != v) {
res.push_back(par[u]);
u = par[u].from();
}
std::reverse(res.begin(), res.end());
if (!directed) {
u = g[eid].to();
while (u != v) {
res.push_back(par[u]);
u = par[u].from();
}
}
return {w, res};
}
//
// s-tid
// O((V + E)logV)
// O(V + E)
std::pair<W, std::vector<edge>> find(bool directed, bool weighted, bool accept_self_loop) {
int N = g.N();
W w = inf;
int r = -1, eid = -1;
if (accept_self_loop) {
for (int v = 0; v < N; v++) {
for (int j = g.begin(v); j < g.end(v); j++) {
if (g[j].to() == v && w < g[j].weight()) {
w = g[j].weight();
r = v;
eid = j;
}
}
}
}
std::vector<W> dist;
std::vector<edge> par;
std::vector<int> semi_root(N, -1);
std::vector<int> ord(N);
std::iota(ord.begin(), ord.end(), 0);
std::random_device seed_gen;
std::mt19937 engine(seed_gen());
std::shuffle(ord.begin(), ord.end(), engine);
for (int v : ord) {
if (weighted) {
std::tie(dist, par) = dijkstra_tree(v);
} else {
std::tie(dist, par) = bfs_tree(v);
}
if (directed) {
for (int i = 0; i < N; i++) {
if (i == v || dist[i] == inf || dist[i] > w) continue;
for (int j = g.begin(i); j < g.end(i); j++) {
if (g[j].to() == v && dist[i] + g[j].weight() < w) {
w = dist[i] + g[j].weight();
eid = j;
r = v;
}
}
}
} else {
std::fill(semi_root.begin(), semi_root.end(), -1);
auto dfs = [&](auto &&dfs, int u, int p, int sr) -> void {
semi_root[u] = sr;
for (int i = g.begin(u); i < g.end(u); i++) {
int to = g[i];
if (to == v || to == p || to == u || dist[to] == inf) continue;
if (par[to].id() == g[i].id()) {
dfs(dfs, to, u, sr);
}
}
};
for (int i = 0; i < N; i++) {
if (i == v || dist[i] == inf) continue;
if (par[i].from() == v) dfs(dfs, i, v, i);
}
for (int i = 0; i < N; i++) {
if (i == v || dist[i] == inf || dist[i] > w) continue;
for (int j = g.begin(i); j < g.end(i); j++) {
int to = g[j];
if (g[j].id() == par[i].id()) continue;
if (semi_root[i] == semi_root[to]) continue;
if (dist[i] + dist[to] + g[j].weight() < w) {
w = dist[i] + dist[to] + g[j].weight();
r = v;
eid = j;
}
}
}
}
}
if (w == inf) return {inf, {}};
if (weighted) {
std::tie(dist, par) = dijkstra_tree(r);
} else {
std::tie(dist, par) = bfs_tree(r);
}
std::vector<edge> res;
res.push_back(g[eid]);
int u = g[eid].from();
while (u != r) {
res.push_back(par[u]);
u = par[u].from();
}
std::reverse(res.begin(), res.end());
if (!directed) {
u = g[eid].to();
while (u != r) {
res.push_back(par[u]);
u = par[u].from();
}
}
return {w, res};
}
};
int main() {
io_init();
int T;
std::cin >> T;
int N, M;
std::cin >> N >> M;
using edge = weighted_labeled_edge<long long>;
std::vector<std::pair<int, edge>> E;
for (int i = 0; i < M; i++) {
int a, b, c;
std::cin >> a >> b >> c;
a--, b--;
E.push_back({a, {a, b, c, i}});
if (T == 0) {
E.push_back({b, {b, a, c, i}});
}
}
cycle_detection_mincost<edge> G(csr<edge>(N, E));
long long w = G.find(T, true, true).first;
std::cout << (w == G.inf ? -1 : w) << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0