제출 #1203267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203267		rafsanamin2020	Cyberland (APIO23_cyberland)	C++17	0 / 100	3103 ms	525768 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

// subtask 1

// double ac(double k, double f)
// {
//     // cout << k << " " << f;
//     if (f == 0)
//     {
//         return 0;
//     }
//     else if (f == 2)
//     {
//         return k / 2;
//     }
//     else
//     {
//         return k;
//     }
// };

// int _(int k)
// {
//     return k == 2 ? 1 : 2;
// }

// 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)
// {
//     double MAX = (5.0e10 + 0.1);
//     vector<vector<double>> C(3, vector<double>(3, MAX));
//     vector<vector<bool>> V(3, vector<bool>(3, false));

//     for (int i = 0; i < M; i++)
//     {
//         C[x[i]][y[i]] = min(C[x[i]][y[i]], (double)c[i]);
//         C[y[i]][x[i]] = min(C[y[i]][x[i]], (double)c[i]);
//         V[x[i]][y[i]] = true;
//         V[y[i]][x[i]] = true;
//     }

//     if ((!V[0][H] && !V[0][_(H)]) || (!V[0][H] && !V[H][_(H)]))
//     {
//         return -1;
//     }

//     // cout << C[0][2] << " ___" << "\n";

//     return min(ac(C[0][_(H)], arr[_(H)]) + C[_(H)][H], C[0][H]);
// }

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, double>>> adj(N);
    vector<double> cost(N, 5.0e16);
    vector<bool> visited(N, false);

    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]});
    }

    for (int i = 0; i < N; i++)
    {
        if (arr[i] == 0)
        {
            cost[i] = 0;
        }
    }

    priority_queue<pair<double, int>> pq;

    cost[0] = 0;
    pq.push({0, 0});

    while (!pq.empty())
    {
        double cst = -pq.top().first;
        int node = pq.top().second;
        pq.pop();

        for (int i = 0; i < adj[node].size(); i++)
        {
            int v = adj[node][i].first;
            double w = adj[node][i].second;

            if (cost[v] < cost[node] + w)
            {

                cost[v] = cost[node] + w;
                pq.push({-w, v});
            }
        }
    }

    return visited[H] ? cost[H] : -1;
}

• 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