제출 #1268476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268476		mikurakill	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	408 ms	59940 KiB

crocodile

#include <queue>
#include <vector>
#include<iostream>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<long long>odl(N, -2);
    vector<long long>prop(N, 0);
    vector<pair<int, int>>graf[N];
    for(int i=0; i<M; i++){
        //                       długość do_wierzchołka
        graf[ R[i][0] ].push_back({L[i], R[i][1]});
        graf[ R[i][1] ].push_back({L[i], R[i][0]});
    }
    priority_queue <pair<long long, int>>kol; // -odl komory, nr komory
    for(int i=0; i<K; i++){
        odl[P[i]] = -1;
        kol.push({0, P[i]});
    }
    while(!kol.empty()){
        auto [o, v] = kol.top();
        kol.pop();
        if(odl[v] == -2){
            odl[v] = -1;
            prop[v] = -o;
            continue;
        }
        if(odl[v] != -1)
            continue;

        if(-o > prop[v])
            odl[v] = -o;
        else
            odl[v] = prop[v];

        for(pair<int, int> i : graf[v]){
            if(odl[i.second] < 0){
                kol.push({-odl[v]-i.first, i.second});
            }
        }
    }
    return odl[0];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11