Submission #1194082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194082		zh_h	사이버랜드 (APIO23_cyberland)	C++17	8 / 100	20 ms	6452 KiB

cyberland

#include<bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> abi) {
    if (n == 2) {
        return c[0];
    }

    vector<vector<pair<int, double>>> edge(n);
    for (int i = 0; i < m; i ++) {
        edge[x[i]].pb({y[i], c[i]});
        edge[y[i]].pb({x[i], c[i]});
    }

    double ans = -1;
    vector<int> visited(n, 0);
    priority_queue<tuple<double, int, int>> pq;
    pq.push(make_tuple(0, 0, 0)); // -w, v, k
    visited[0] ++;
    while (!pq.empty()) {
        tuple<double, int, int> cur = pq.top(); pq.pop();
        double w = get<0>(cur); w *= -1;
        int v = get<1>(cur), k = get<2>(cur);
        if (v == h) {
            ans = w;
            break;
        }

        for (auto [cv, cw] : edge[v]) {
            if (visited[cv] == 2) {continue;}
            visited[cv] ++;

            if (abi[cv] == 0) {
                pq.push({make_tuple(0, cv, k)});
            }
            else if (abi[cv] == 2) {
                if (k > 0) pq.push({make_tuple(-(w+cw)/2, cv, k-1)});
                pq.push({make_tuple(-(w+cw), cv, k)});
            }
            else {
                pq.push({make_tuple(-(w+cw), cv, k)});
            }
        }
    }

    return ans;
}

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