제출 #1228046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228046		Dzadzo	사이버랜드 (APIO23_cyberland)	C++20	0 / 100	238 ms	26880 KiB

cyberland

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

double solve(int n, int m, int K, int h,
             vector<int> x, vector<int> y, vector<int> c,
             vector<int> arr)
{
    // build undirected graph
    vector<vector<pair<int,int>>> adj(n);
    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]});
    }

    // dist[v][k] = minimum cost from h→v having used exactly k "doublings"
    const double INF = 1e15;
    vector<vector<double>> dist(n, vector<double>(31, INF));
    dist[h][0] = 0.0;

    // min-heap of (current_distance, node, used_k)
    using T = tuple<double,int,int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.emplace(0.0, h, 0);

    while(!pq.empty()){
        auto [cd, v, k] = pq.top(); 
        pq.pop();
        // skip stale
        if (cd > dist[v][k]) continue;

        for(auto &e : adj[v]){
            int to = e.first, w = e.second;
            // 1) normal move, no doubling
            double nd = cd + w;
            if (nd < dist[to][k]){
                dist[to][k] = nd;
                pq.emplace(nd, to, k);
            }
            // 2) if city 'to' is type‑2, you may spend one doubling
            if (arr[to] == 2 && k < 30){
                double nd2 = 2.0 * nd;
                if (nd2 < dist[to][k+1]){
                    dist[to][k+1] = nd2;
                    pq.emplace(nd2, to, k+1);
                }
            }
        }
    }

    // quick reachability check (undirected)
    vector<char> vis(n, 0);
    function<void(int)> dfs = [&](int u){
        vis[u] = 1;
        for(auto &e: adj[u]){
            if (!vis[e.first]) dfs(e.first);
        }
    };
    dfs(0);
    if (!vis[h]) return -1;       // no path between 0 and h

    // now compute best possible answer
    double ans = INF;
    // first consider reaching node 0 itself
    double scale = 1.0;
    for(int k = 0; k <= min(K, 30); k++){
        ans = min(ans, dist[0][k] / scale);
        scale *= 2.0;
    }
    // then consider every other special city i with arr[i]!=0
    for(int i = 1; i < n; i++){
        if (arr[i] != 0 && vis[i]){
            double t = 1.0;
            for(int k = 0; k <= min(K, 30); k++){
                ans = min(ans, dist[i][k] / t);
                t *= 2.0;
            }
        }
    }
    return ans;
}

• 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