제출 #1135712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135712		_uros9	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	554 ms	51560 KiB

crocodile

///100 poena
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

const int MAXN=100009,INF=2000000000;
vector<pair<int,int>> graf[MAXN];
int prvi[MAXN],drugi[MAXN];
int rez[MAXN];
bool vi[MAXN];


int val(int node){
    return drugi[node];
}



int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for(int i=0; i<N; i++) rez[i]=INF;
    for(int i=0; i<M; i++){
        int a=R[i][0],b=R[i][1],w=L[i];
        graf[a].push_back({b,w});
        graf[b].push_back({a,w});
    }
    for(int i=0; i<N; i++) prvi[i]=drugi[i]=INF;
    priority_queue<pair<int,int>> red;
    for(int i=0; i<K; i++) red.push({0,P[i]});
    while(red.size()){
        int node=red.top().second,tr=-red.top().first;
        red.pop();
        if(vi[node]) continue;
        vi[node]=true;
        rez[node]=tr;
        for(auto x:graf[node]){
            int nw=rez[node]+x.second;
            if(nw<=prvi[x.first]){drugi[x.first]=prvi[x.first];prvi[x.first]=nw;continue;}
            if(nw<=drugi[x.first]){drugi[x.first]=nw; continue;}
        }
        for(auto x:graf[node])
            red.push({-val(x.first),x.first});
    }
    return rez[0];

}

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