Submission #249736

#	Time	Username	Problem	Language	Result	Execution time	Memory
249736		eohomegrownapps	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	1 ms	512 KiB

crocodile

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

vector<vector<pair<int,int>>> adjlist; //val,node
int n,k;
vector<int> exits; //k of them
int INF = 1e9;
int dijkstra(){
    //source is 0
    vector<pair<int,int>> distances(n,{INF,INF}); //second then first
    priority_queue<pair<pair<int,int>,int>,vector<pair<pair<int,int>,int>>,greater<pair<pair<int,int>,int>>> pq;
    //second,first
    for (int i = 0; i<k; i++){
        distances[exits[i]]={0,0};
        pq.push({{0,0},exits[i]});
    }
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        /*cout<<"======\n";
        cout<<f.second<<'\n';
        for (auto p : distances){
            cout<<p.first<<" "<<p.second<<'\n';
        }*/
        //cout<<"check: "<<distances[f.second].first<<" "<<distances[f.second].second<<", "<<f.first.first<<" "<<f.first.second<<'\n';
        if (distances[f.second]<f.first){
            continue; //can't remember this condition
        }
        for (auto p : adjlist[f.second]){
            int dist = p.first;
            int node = p.second;
            int newval = distances[f.second].first+dist;
            //cout<<newval<<'\n';
            if (newval<=distances[node].second){
                distances[node].first=distances[node].second;
                distances[node].second=newval;
                pq.push({distances[node],node});
            } else if (newval<=distances[node].first){
                distances[node].first=newval;
                pq.push({distances[node],node});
            }
        }
    }
    return distances[0].first;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n=N;k=K;
    adjlist.resize(n);
    for (int i = 0; i<M; i++){
        adjlist[R[i][0]].push_back({L[i],R[i][1]});
        adjlist[R[i][1]].push_back({L[i],R[i][0]});
    }
    exits = vector<int>(P,P+k);
    return dijkstra();
}

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