oj.uz

답안 #708055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708055 2023-03-11T02:29:09 Z Github 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 3 ms 340 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define INF 1e9

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    int n = N, m = M, k = K;
    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < m; i++){
        graph[R[i][0]-1].push_back({R[i][1]-1, L[i]});
        graph[R[i][1]-1].push_back({R[i][0]-1, L[i]});
    }
    int dist[n][2];
    for (int i = 0; i < n; i++){
        dist[i][0] = INF, dist[i][1] = INF;
    }
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    for (int i = 0; i < k; i++){
        dist[P[i]-1][0] = 0;
        dist[P[i]-1][1] = 0;
        pq.push({0, {P[i]-1, 1}});
    }
    while (!pq.empty()){
        int cur_dis = pq.top().first, u = pq.top().second.first, type = pq.top().second.second;
        pq.pop();
        if (cur_dis != dist[u][type]){
            continue;
        }
        for (pair<int, int> p: graph[u]){
            int v = p.first, w = p.second;
            if (dist[v][0] > w + cur_dis){
                dist[v][1] = dist[v][0];
                dist[v][0] = w+cur_dis;
                pq.push({dist[v][1], {v, 1}});
            }else if (dist[v][1] > w + cur_dis){
                dist[v][1] = w + cur_dis;
                pq.push({dist[v][1], {v, 1}});
            }
        }
    }
    return dist[0][1];
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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