結果

問題 No.1320 Two Type Min Cost Cycle
ユーザー umimel
提出日時 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();
      |                  ^

ソースコード

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

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0