제출 #754950

#제출 시각아이디문제언어결과실행 시간메모리
754950Zanite사이버랜드 (APIO23_cyberland)C++17
100 / 100
1507 ms11476 KiB
#include "cyberland.h" // 赤コーダーになりたい // お願い いいですか? #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> // Pragmas // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // Namespaces using namespace std; using namespace __gnu_pbds; // Data types using si = short int; using ll = long long; using lll = __int128; using ld = long double; // Pairs using pii = pair<int, int>; using psi = pair<si, si>; using pll = pair<ll, ll>; using plll = pair<lll, lll>; using pld = pair<ld, ld>; #define fi first #define se second // For #define Frue(i, n, N) for (int i = (n); i <= (N); i++) #define Fru(i, n, N) for (int i = (n); i < (N); i++) #define Frde(i, n, N) for (int i = (n); i >= (N); i--) #define Frd(i, n, N) for (int i = (n); i > (N); i--) // PBDS template<typename Z> using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>; // Various outputs template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) { return os << '(' << p.fi << ',' << p.se << ')'; } template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) { os << '{'; bool _first = 1; for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;} return os << '}'; } template<typename Z, unsigned long long sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) { os << '{'; bool _first = 1; for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;} return os << '}'; } // Quick macro functions #define sqr(x) ((x)*(x)) #define debug(x) cout << #x << " = " << (x) << '\n' #define debugV(v, x) cout << #v << "[" << (x) << "] = " << (v[x]) << '\n' #define rrebug(x) cerr << #x << " = " << (x) << '\n' #define rrebugV(v, x) cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n' #define All(x) x.begin(), x.end() #define Sort(x) sort(All(x)) #define Reverse(x) reverse(All(x)) #define Uniqueify(x) Sort(x); x.erase(unique(All(x)), x.end()) #define RandomSeed chrono::steady_clock::now().time_since_epoch().count() #define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++) // Check min and max template<typename Z> void chmin(Z &a, Z b) {a = min(a, b);} template<typename Z> void chmax(Z &a, Z b) {a = max(a, b);} // Modular arithmetic template<int MOD> class ModInt { public: int v; ModInt() : v(0) {} ModInt(long long _v) { v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD)); if (v < 0) v += MOD; } friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;} friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;} friend bool operator< (const ModInt &a, const ModInt &b) {return a.v < b.v;} friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;} friend bool operator> (const ModInt &a, const ModInt &b) {return a.v > b.v;} friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;} ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;} ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;} ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;} ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);} friend ModInt pow(ModInt a, long long x) { ModInt res = 1; for (; x; x /= 2, a *= a) if (x & 1) res *= a; return res; } friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);} ModInt operator+ () const {return ModInt( v);} ModInt operator- () const {return ModInt(-v);} ModInt operator++() const {return *this += 1;} ModInt operator--() const {return *this -= 1;} friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;} friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;} friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;} friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;} friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;} friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;} }; const int ModA = 998244353; const int ModC = 1e9 + 7; using MintA = ModInt<ModA>; using MintC = ModInt<ModC>; // Other constants const double INF = 1e18; const double iINF = 1e9; const double EPS = 1e-9; const double iEPS = 1e-6; const bool ge(double x, double y) {return ((x - y) >= EPS);} const bool geq(double x, double y) {return ((x - y) >= -EPS);} using pdi = pair<double, int>; void Dijkstra(int N, vector<vector<pii>> &adj, vector<int> &start, vector<double> &dist) { priority_queue<pdi, vector<pdi>, greater<pdi>> PQ; vector<bool> vis(N, false); for (auto i : start) PQ.push({dist[i], i}); while (!PQ.empty()) { auto [cdist, cur] = PQ.top(); PQ.pop(); if (vis[cur]) continue; // cout << make_pair(cdist, cur) << '\n'; vis[cur] = true; for (auto &[nxt, w] : adj[cur]) { if (ge(dist[nxt], dist[cur] + w)) { dist[nxt] = dist[cur] + w; PQ.push({dist[nxt], nxt}); } } // debug(dist); } } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { K = min(K, 100); vector<vector<pii>> adj(N, vector<pii>()); for (int i = 0; i < M; i++) { adj[x[i]].push_back({y[i], c[i]}); adj[y[i]].push_back({x[i], c[i]}); } adj[H].clear(); vector<int> stReach = {0}; vector<double> rd(N, INF); rd[0] = 0; Dijkstra(N, adj, stReach, rd); vector<bool> reach(N, false); for (int i = 0; i < N; i++) { if (geq(rd[i], INF)) continue; reach[i] = true; } vector<int> stInit = {0}, stDiv = {}; for (int i = 1; i < N; i++) { if (arr[i] == 0 && reach[i]) stInit.push_back(i); if (arr[i] == 2 && reach[i]) stDiv.push_back(i); } vector<double> dist(N, INF); for (auto i : stInit) dist[i] = 0; // K = 0 Dijkstra(N, adj, stInit, dist); double ans = dist[H]; // debug(dist); for (int i = 1; i <= K; i++) { vector<double> nd(N, INF); vector<int> curSt; for (auto i : stDiv) { if (geq(dist[i], INF)) continue; double cur = dist[i] / 2; // debug(cur); for (auto &[nxt, w] : adj[i]) { nd[nxt] = min(nd[nxt], cur + w); curSt.push_back(nxt); } } swap(nd, dist); Uniqueify(curSt); Dijkstra(N, adj, curSt, dist); ans = min(ans, dist[H]); // debug(dist); } if (geq(ans, INF)) ans = -1; return ans; } #ifdef Zanite int main() { int T; assert(1 == scanf("%d", &T)); while (T--){ int N,M,K,H; assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H)); std::vector<int> x(M); std::vector<int> y(M); std::vector<int> c(M); std::vector<int> arr(N); for (int i=0;i<N;i++) assert(1 == scanf("%d", &arr[i])); for (int i=0;i<M;i++) assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i])); printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr)); } } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...