Submission #1253502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253502		anfi	Cyberland (APIO23_cyberland)	C++20	20 / 100	1040 ms	2162688 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;

const double INF = 1e18;

double solve(int N, int M, int K, int H,
             vector<int> x, vector<int> y, vector<int> c,
             vector<int> arr) {

    vector<vector<double>> dist(N, vector<double>(K+1, INF));
    using T = pair<double, pair<int,int>>;
    priority_queue<T, vector<T>, greater<T>> pq;

    dist[0][0] = 0;
    pq.push({0.0, {0, 0}});

    while (!pq.empty()) {
        auto [d, uc] = pq.top(); pq.pop();
        int u = uc.first, used = uc.second;
        if (d > dist[u][used]) continue;
        if (u == H) break;

        for (int i = 0; i < M; i++) {
            int v = -1, w = -1;
            if (x[i] == u)      { v = y[i]; w = c[i]; }
            else if (y[i] == u) { v = x[i]; w = c[i]; }
            else continue;

            double nd = d + w;
            int nk = used;

            if (arr[v] == 0) {
                nd = 0;
            }
            else if (arr[v] == 2 && used < K) {
                nd = nd / 2.0;
                nk = used + 1;
            }


            if (nd + 1e-12 < dist[v][nk]) {
                dist[v][nk] = nd;
                pq.push({nd, {v, nk}});
            }
        }
    }

    double ans = INF;
    for (int k = 0; k <= K; k++) {
        ans = min(ans, dist[H][k]);
    }
    if (ans >= INF/2) return -1;
    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3