Submission #1252636

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

cyberland

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double inf = 1e30;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    double ans = 1e30;
    vector<pair<int,int>> adj[N];
    vector<vector<double>> dp(N, vector<double>(K+1, 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]});
    }
    vector<int> a = arr;
    priority_queue<tuple<double,int,int>, vector<tuple<double, int, int>>, greater<tuple<double,int,int>>> pq;
    dp[0][0] = 0.0;
    pq.push({0.0, 0,0});
    while(!pq.empty()){
        auto [c, u, pos] = pq.top(); pq.pop();
        if(c > dp[u][pos]+1e-9) continue;
        for(auto &[v, w] : adj[u]){
            double cost = c+w;
            if(dp[v][pos] > cost+1e-9){
                dp[v][pos] = cost;
                pq.push({cost, v, pos});
            }
            if(a[v] == 0){
                if(dp[v][pos] > 0.0+1e-9){
                    dp[v][pos] = 0.0;
                    pq.push({0.0, v, pos});
                }
            }
            if(a[v] == 2 && pos < K){
                double co = (c+w)/2.0;
                if(dp[v][pos+1] > co+1e-9){
                    dp[v][pos+1] = co;
                    pq.push({co, v, pos+1});
                }
            }
        }
    }
    for(int i = 0; i <= K; i++) ans = min(ans, dp[H][i]);
    return (ans >= inf/2 ? -1.0 : ans);
}

/*
signed main(){
    int n,m; cin >> n >> m;
    vector<pair<int,int>> adj[n+3]; 
    vector<vector<int>> dp(n+3, vector<int>(2, mod));
    dp[1][0] = 0;
    for(int i = 0,u,v,c; i < m; i++){
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
    }
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
    pq.push({0, 1, 0});
    while(!pq.empty()){
        auto [c, u, cek] = pq.top(); pq.pop();
        if(dp[u][cek] < c) continue;
        for(auto &[v, w] : adj[u]){
            if(dp[v][cek] > c+w){
                dp[v][cek] = c+w;
                pq.push({dp[v][cek], v,cek});
            }
            if(cek == 0){
                int dc = w/2;
                if(dp[v][1] > dc+c){
                    dp[v][1] = dc+c;
                    pq.push({dp[v][1], v, 1});
                }
            }
        }
    }
    cout << dp[n][1];
}*/

• 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