제출 #1253940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253940		anfi	Cyberland (APIO23_cyberland)	C++20	15 / 100	260 ms	7092 KiB

cyberland

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
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){
    double ans = 1e18;
    K = min(K, 100);
    vector<pair<int,int>> adj[N];
    vector<double> dp(N, inf),tmp(N, inf);
    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]});
    }
    priority_queue<pair<double, int>> pq;
    for(int i = 0; i <= K; i++){
        vector<double> tmp(N, inf);
        if(i){
            for(int j = 0; j < N; j++){
                if(arr[j] == 1 || dp[j] == inf) continue;
                if(arr[j] == 0) tmp[j] = 0.0;
                pq.push({-dp[j]/2.0, j});
            }
        }else pq.push({0.0, 0});

        while(!pq.empty()){
            auto [c, u] = pq.top(); pq.pop();
            c = -c;
            if(u == H) continue;
            for(auto &[v, w] : adj[u]){
                double cost = c+w;
                if(tmp[v] > cost){
                    if(arr[i] == 0) tmp[v] = 0.0;
                    else tmp[v] = cost;
                    pq.push({-tmp[v], v});
                }          
            }
        }
        ans = min(ans, tmp[H]);
        if(i == 0 && tmp[H]== inf) break;
        swap(tmp, dp);
    }
    return (ans >= inf/2 ? -1.0 :ans);
}

• Subtask 1: 0 / 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