Submission #1257136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257136		antonn	Cyberland (APIO23_cyberland)	C++20	In queue	0 ms	0 KiB

cyberland

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;

struct kek {
    double dist;
    int node;
    int cnt;
};

bool operator < (const kek &a, const kek &b) {
    return a.dist < b.dist;
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<vector<pair<int, int>>> g(n);
    vector<int> t(n);
    iota(all(t), 0);
    auto root = [&](auto self, int x) {
        if (x == t[x]) return x;
        return t[x] = self(self, t[x]);
    };
    auto join = [&](int x, int y) -> void {
        x = root(root, x), y = root(root, y);
        t[x] = y;
    };
    for (int i = 0; i < m; i++) {
         g[x[i]].push_back({y[i], c[i]});
         g[y[i]].push_back({x[i], c[i]});
         join(x[i], y[i]);
    }
    if (root(root, 0) != root(root, h)) {
        return -1;
    }
    priority_queue<kek> pq;
    vector<vector<double>> dist(n, vector<double>(k + 1, 1e18));
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            dist[i][0] = 0;
            pq.push({0, i, 0});
        }
    }
    while (!pq.empty()) {
        int u = pq.top().node;
        int kk = pq.top().cnt;
        pq.pop();
        if (u == h) continue;
        for (auto [v, c] : g[u]) {
            if (dist[u][kk] + c < dist[v][kk]) {
                dist[v][kk] = dist[u][kk] + c;
                if (arr[v] == 0) dist[v][kk] = 0;
                pq.push({dist[v][kk], v, kk});
            }
            if (v != h && arr[v] == 2 && kk + 1 <= k && (dist[u][kk] + c) / 2 < dist[v][kk + 1]) {
                dist[v][kk + 1] = (dist[u][kk] + c) / 2;
                pq.push({dist[v][kk + 1], v, kk + 1});
            }
        }
    }
    double res = 1e18;
    for (int i = 0; i <= k; i++) res = min(res, dist[h][i]);
    return res;
}