Submission #983227

#	Time	Username	Problem	Language	Result	Execution time	Memory
983227		h_squared	Cyberland (APIO23_cyberland)	C++17	97 / 100	3063 ms	182948 KiB

cyberland

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


struct node{
    int u,k;double cost;
};
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    
    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]});
    }
    K=min(K,150);
    vector<vector<double>>d(N,vector<double>(K+1,1e18));
    d[0][0]=0;
    auto cmp=[](node& a,node &b){return a.cost>b.cost;};
    priority_queue<node,vector<node>,decltype(cmp)>pq(cmp);
    pq.push({0,0,0});
    double ans=1e18;
    while(!pq.empty()){
        auto [u,k,cost]=pq.top();pq.pop();
        if(d[u][k]<cost)continue;
        if(u==H){
            ans=min(ans,cost);
            continue;
        }
        for(auto [v,w]:adj[u]){
            double now=cost+w;
            if(arr[v]==0){
                now=0;
                if(now<d[v][0]){
                    d[v][0]=now;
                    pq.push({v,0,now});
                }
            }
            else{
                if(now<d[v][k]){
                    d[v][k]=now;
                    pq.push({v,k,now});
                }
                if(arr[v]==2 && k<K){
                    now=now/2;
                    if(now<d[v][k+1]){
                        d[v][k+1]=now;
                        pq.push({v,k+1,now});
                    }
                }
            }
        }
    }
    if(ans==1e18)return -1;
    else return ans;

}

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