Submission #919112

#TimeUsernameProblemLanguageResultExecution timeMemory
919112vjudge1Deda (COCI17_deda)C++17
0 / 140
24 ms26820 KiB
#include <bits/stdc++.h> using i64 = long long; struct DSU { int n; std::vector<int> par; DSU(int _n) : n(_n) { par.resize(n); std::iota(par.begin(), par.end(), 0); } int get(int x) { if(par[x] == x) { return x; } return par[x] = get(par[x]); } bool same(int a, int b) { return get(a) == get(b); } bool unite(int u, int v) { if(same(u, v)) { return false; } u = get(u); v = get(v); par[u] = v; return true; } }; 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) { DSU dsu(N); std::vector<std::pair<int, int>> adj[N]; for(int i = 0; i < M; i++) { dsu.unite(x[i], y[i]); adj[x[i]].emplace_back(y[i], c[i]); adj[y[i]].emplace_back(x[i], c[i]); } if(!dsu.same(0, H)) { return -1; } K = std::min(100, K); std::vector<double> pw(K + 1, 1); for(int i = 1; i <= K; i++) { pw[i] = pw[i - 1] / 2; } using T = std::tuple<int, int, int>; std::priority_queue<T, std::vector<T>, std::greater<T>> pq; pq.emplace(0, H, 0); std::vector dist(N, std::vector<double> (K + 1, -1)); while(!pq.empty()) { auto [cost, node, bound] = pq.top(); pq.pop(); if(dist[node][bound] != -1) { continue; } dist[node][bound] = cost; if(arr[node] == 0) { return cost; } else if(node == 0) { return cost; } for(auto [child, w] : adj[node]) { pq.emplace(cost + w * pw[bound], child, bound); if(arr[child] == 2) { pq.emplace(cost + w * pw[bound + 1], child, bound + 1); } } } return -1; } void solve() { int N, M, K; std::cin >> N >> M >> K; int H; std::cin >> H; std::vector<int> arr(N); for(int i = 0; i < N; i++) { std::cin >> arr[i]; } std::vector<int> x(M), y(M), c(M); for(int i = 0; i < M; i++) { std::cin >> x[i] >> y[i] >> c[i]; } std::cout << solve(N, M, K, H, x, y, c, arr); return; } signed main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int t = 1; //std::cin >> t; for(int i = 1; i <= t; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...