oj.uz

답안 #990692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990692 2024-05-31T03:28:24 Z Ibrohim0704 사이버랜드 (APIO23_cyberland) C++17
0 / 100
 929 ms 2097152 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Node {
    int country;
    int passing_time;
    int divide_count;

    Node(int c, int t, int d) : country(c), passing_time(t), divide_count(d) {}
    
    bool operator<(const Node& other) const {
        return passing_time > other.passing_time;
    }
};

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<vector<pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[x[i]].push_back({y[i], c[i]});
        graph[y[i]].push_back({x[i], c[i]});
    }

    priority_queue<Node> pq;
    pq.push(Node(0, 0, 0));

    vector<vector<vector<int>>> dp(N, vector<vector<int>>(K + 1, vector<int>(N, INT_MAX)));

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        if (curr.country == H) {
            return curr.passing_time;
        }

        if (dp[curr.country][curr.divide_count][curr.passing_time] != INT_MAX) {
            continue;
        }
        dp[curr.country][curr.divide_count][curr.passing_time] = curr.passing_time;

        for (auto& neighbor : graph[curr.country]) {
            int next_country = neighbor.first;
            int next_time = curr.passing_time + neighbor.second;
            int next_divide_count = curr.divide_count;

            if (arr[next_country] == 2 && next_divide_count < K) {
                next_time /= 2;
                next_divide_count++;
            }

            pq.push(Node(next_country, next_time, next_divide_count));
        }
    }

    return -1; 
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 121 ms 240104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 929 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 49776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 123 ms 171344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 41 ms 56708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 702 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -