제출 #1175901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175901		Ariadna	Cyberland (APIO23_cyberland)	C++20	0 / 100	1058 ms	2162688 KiB

cyberland

#include <bits/stdc++.h>
#define pb push_back
#define se second
#define fi first
using namespace std;

const int MAX_N = 1e5;
vector<vector<pair<int, int>>> adj;

double dijkstra(int n, int k, int h, vector<int>& arr) {
    vector<vector<double>> dist(n, vector<double>(k+1, 1e9)); // mínima distància a i gastant j vegades
    vector<double> dist2(n, 1e9);
    priority_queue<pair<int, pair<int, int>>> pq;
    dist[0][0] = 0;
    pq.push({0, {0, 0}});
    while (!pq.empty()) {
        double d = -pq.top().fi;
        int u = pq.top().se.fi;
        int i = pq.top().se.se;
        pq.pop();
        if (dist[u][i] != d) continue;
        if (u == h) continue;
        for (auto v: adj[u]) {
            if (!arr[v.fi]) {
                dist[v.fi][i] = 0;
                if (dist2[v.fi] > 0) {
                    dist2[v.fi] = 0;
                    pq.push({0, {v.fi, 0}});
                }
            } else {
                if (dist[v.fi][i] > d+v.se) {
                    dist[v.fi][i] = d+v.se;
                    pq.push({-dist[v.fi][i], {v.fi, i}});
                }
                if (arr[v.fi] == 2 && i+1 <= k) {
                    if (dist[v.fi][i+1] > (double)(d+v.se)/2) {
                        dist[v.fi][i+1] = (double)(d+v.se)/2;
                        pq.push({-dist[v.fi][i+1], {v.fi, i+1}});
                    }
                }
            }
        }
    }

    double ans = 1e9;
    for (int i = 0; i <= k; ++i) ans = min(ans, dist[h][i]);
    return ans;
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    adj = vector<vector<pair<int, int>>>(N);
    for (int i = 0; i < M; ++i) {
        adj[x[i]].pb({y[i], c[i]});
        adj[y[i]].pb({x[i], c[i]});
    }
    return dijkstra(N, K, H, arr);
}

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