제출 #969378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969378		CDuong	사이버랜드 (APIO23_cyberland)	C++17	0 / 100	997 ms	2097152 KiB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"
#define i64 long long
#define ff first
#define ss second

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) {
    vector<vector<int>> G(n);
    for (int i = 0; i < m; ++i) {
        G[x[i]].emplace_back(i);
        G[y[i]].emplace_back(i);
    }

    // cout << n << " " << m << endl;

    vector<vector<double>> dis(n, vector<double>(K, 1e18));
    priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<pair<double, pair<int, int>>>> pq;
    
    dis[0][0] = 0;
    pq.emplace(0, pair(0, 0));

    while (not pq.empty()) {
        auto w = pq.top().ff;
        auto v = pq.top().ss.ff;
        auto used = pq.top().ss.ss;
        pq.pop();

        // cout << w << " " << v << " " << used << endl;

        if (w != dis[v][used]) continue;

        double nw;
        for (int eidx : G[v]) {
            int u = x[eidx] ^ y[eidx] ^ v;
            if (arr[u] == 0) {
                nw = 0;
                if (dis[u][used] > nw) {
                    dis[u][used] = nw;
                    pq.emplace(nw, pair(u, used));
                }
            }
            if (arr[u] == 2 and used < K) {
                nw = (w + c[eidx]) / 2;
                if (dis[u][used + 1] > nw) {
                    dis[u][used + 1] = nw;
                    pq.emplace(nw, pair(u, used + 1));
                }
            }
            nw = w + c[eidx];
            if (dis[u][used] > nw) {
                dis[u][used] = nw;
                pq.emplace(nw, pair(u, used));
            }
        }
    }
    double res = 1e18;
    for (int i = 0; i <= K; ++i) res = min(res, dis[H][i]);
    return res;
}

// int main() {
//     int T;
//     assert(1 == scanf("%d", &T));
//     while (T--){
//         int N,M,K,H;
//         assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
//         std::vector<int> x(M);
//         std::vector<int> y(M);
//         std::vector<int> c(M);
//         std::vector<int> arr(N);
//         for (int i = 0; i < N; i++) assert(1 == scanf("%d", &arr[i]));
//         for (int i = 0; i < M; i++) assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
//         printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
//     }
// }

• 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