Submission #438438

#	Time	Username	Problem	Language	Result	Execution time	Memory
438438		Deepesson	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1213 ms	65248 KiB

crocodile

#include <bits/stdc++.h>
#define MAX 101000
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
int travel_plan(int N,int M,int R[][2],int* L,int K,int* P)
{
    for(auto&x:con)x.clear();
    for(int i=0;i!=M;++i){
        int a=R[i][0],b=R[i][1],c=L[i];
        con[a].push_back({b,c});
        con[b].push_back({a,c});
    }
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
    int peso_min[N]={};
    int visitas[N]={};
    for(int i=0;i!=K;++i){
        int x=P[i];
        visitas[x]=1;queue.push({0,x});
    }
    while(queue.size()){
        auto _=queue.top();
        queue.pop();
        if(!visitas[_.second]){
            ++visitas[_.second];
        }else if(visitas[_.second]==1){
            ++visitas[_.second];
            peso_min[_.second]=_.first;
            for(auto&k:con[_.second]){
                queue.push({k.second+_.first,k.first});
            }
        }
    }
    return peso_min[0];
}

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