結果
| 問題 |
No.1320 Two Type Min Cost Cycle
|
| コンテスト | |
| ユーザー |
 K U
|
| 提出日時 | 2024-05-17 20:42:56 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,234 bytes |
| コンパイル時間 | 5,002 ms |
| コンパイル使用メモリ | 283,804 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-12-20 12:59:10 |
| 合計ジャッジ時間 | 16,913 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 3 |
| other | RE * 57 |
ソースコード
#pragma GCC target("avx512f")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops") // ループの部分展開
#include <bits/stdc++.h>
// #include <atcoder/all>
// using namespace atcoder;
#ifdef LOCAL
#include <debug.h>
#define dbg(...) debug::dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) void(0)
#endif
using namespace std;
// #define int ll
#define rep(i, a, b) for(auto i=static_cast<signed>(a), i##_end__=static_cast<signed>(b); i < i##_end__; i++)
#define rep_r(i, a, b) for(auto i=static_cast<signed>(a), i##_end__=static_cast<signed>(b); i >= i##_end__; i--)
#define fore(i, a) for(auto& i: a)
#define forei(i, it, a) for(auto [i, it] = std::pair{0, std::begin(a)}; it != std::end(a); i++, it++)
#define all(x) std::begin(x), std::end(x)
using ll = long long; // __int128;
using ull = unsigned long long;
template<class T> using priority_queue_asc = priority_queue<T, vector<T>, greater<T>>;
template<class T> ostream& operator<<(ostream& os, const vector<T>& v){ rep(i, 0, v.size()){ os << (i == 0 ? "" : " ") << v[i]; } return os; }
template<class T, class S> istream& operator>>(istream& is, pair<T, S>& p) { is >> p.first >> p.second; return is; }
template<class T> istream& operator>>(istream& is, vector<T>& v) { fore(e, v){ is >> e; } return is; }
template<class C> int siz(const C& c) { return static_cast<int>(c.size()); }
template<class T, size_t N> constexpr int siz(const T (&)[N]) { return static_cast<int>(N); }
template<class A, class V> constexpr void fil(A& a, const V &v){ if constexpr(is_array_v<A>) for(auto& s: a) fil(s, v); else a = v; };
template<class V> constexpr auto vct(size_t n, const V& v){ return vector(n, v); } template <class... A> constexpr auto vct(size_t n, A... a){ return vector(n, vct(a...)); }
template<class T, class S> constexpr bool chmax(T& a, S b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> constexpr bool chmin(T& a, S b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> constexpr T pow2(T x){ return x * x; }
template<class T, class S> constexpr T divceil(T x, S div) { return (x % div == 0) ? x / div : (x >= 0) ? (x / div) + 1 : -((-x) / div); }
template<class T, class S> constexpr T divfloor(T x, S div){ return (x % div == 0) ? x / div : (x >= 0) ? (x / div) : -((-x) / div) - 1; }
template<class T, class S> inline void outif(bool c, T t, S f){ if(c) cout << t << endl; else cout << f << endl; }
inline void yesno(bool x){ cout << (x ? "Yes" : "No") << endl; }
constexpr long long INF = 1LL << 60; // 1.15e18
constexpr int MOD = (int)1e9 + 7;
using Type = ll;
constexpr int MAX_N = 2048;
int N;
Type g[MAX_N][MAX_N];
// 最短路木 - 密グラフバージョン O(N^2)
// 戻り値: d[v]=最短距離(重み), p[v]=親頂点(rootの場合、-1), l[v]=通る経路の色分け。最初の頂点(root直下の頂点番号)
tuple<vector<Type>, vector<int>, vector<int>> shortest_path_tree(int root, Type inf = numeric_limits<Type>::max()){
vector<Type> d(N, inf);
vector<int> p(N, -1), l(N, -1);
vector<bool> done(N);
d[root] = 0;
while(true){
int v = -1;
Type mn = inf;
rep(i, 0, N) if(!done[i] && d[i] < mn) v = i, mn = d[i];
if(v == -1) break;
done[v] = true;
rep(i, 0, N){
bool f = done[i] || i == v || g[v][i] >= inf || d[i] <= mn + g[v][i];
d[i] = f ? d[i] : mn + g[v][i];
p[i] = f ? p[i] : v;
l[i] = f ? l[i] : v == root ? i : l[v];
}
}
return {d, p, l};
}
// 無向グラフ 最小サイクル - 密グラフバージョン O(N^2)
pair<Type, vector<int>> shortest_cycle_undirected(int root, Type inf = numeric_limits<Type>::max()){
auto [d, p, l] = shortest_path_tree(root, inf);
Type mn = inf;
int mu = -1, mv = -1;
rep(u, 0, N){
if(u == root || d[u] >= inf) continue;
rep(v, u + 1, N){
bool f = v == root || l[u] == l[v] || d[v] >= inf || g[u][v] >= inf || mn <= d[u] + d[v] + g[u][v];
mn = f ? mn : d[u] + d[v] + g[u][v];
mu = f ? mu : u;
mv = f ? mv : v;
}
}
if(mn == inf) return {inf, {}};
vector<int> path;
int v = mu;
while(v != root) path.push_back(v), v = p[v];
path.push_back(root);
reverse(all(path));
v = mv;
while(v != root) path.push_back(v), v = p[v];
return {mn, path};
}
pair<Type, vector<int>> shortest_cycle_undirected_all(Type inf = numeric_limits<Type>::max()){
Type mn = inf;
vector<int> path;
rep(i, 0, N){
auto [m, p] = shortest_cycle_undirected(i, inf);
if(mn > m) mn = m, path = p;
}
return {mn, path};
}
// 有向グラフ 最小サイクル - 密グラフバージョン O(N^2)
pair<Type, vector<int>> shortest_cycle_directed(int root, Type inf = numeric_limits<Type>::max()){
auto [d, p, l] = shortest_path_tree(root, inf);
Type mn = inf;
int v = -1;
rep(i, 0, N){
bool f = i == root || d[i] >= inf || g[i][root] >= inf || mn <= d[i] + g[i][root];
mn = f ? mn : d[i] + g[i][root];
v = f ? v : i;
}
if(mn == inf) return {inf, {}};
vector<int> path;
while(v != root) path.push_back(v), v = p[v];
path.push_back(root);
reverse(all(path));
return {mn, path};
}
pair<Type, vector<int>> shortest_cycle_directed_all(Type inf = numeric_limits<Type>::max()){
Type mn = inf;
vector<int> path;
rep(i, 0, N){
auto [m, p] = shortest_cycle_directed(i, inf);
if(mn > m) mn = m, path = p;
}
return {mn, path};
}
void _main() {
int T, M;
cin >> T >> N >> M;
constexpr auto inf = numeric_limits<ll>::max();
fil(g, inf);
rep(i, 0, M){
int u, v, w;
cin >> u >> v >> w;
u--; v--;
g[u][v] = w;
if(T == 0) g[v][u] = w;
}
if(T == 0){
auto [mn, path] = shortest_cycle_undirected_all(inf);
outif(mn < inf, mn, -1);
}
else{
auto [mn, path] = shortest_cycle_directed_all(inf);
outif(mn < inf, mn, -1);
}
}
signed main() {
cin.tie(nullptr); ios::sync_with_stdio(false);
cout << fixed << setprecision(15); cerr << fixed << setprecision(15);
_main();
}