제출 #565559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565559		qwerasdfzxcl	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	610 ms	66460 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Vertex{
    int i, d;
    Vertex(){}
    Vertex(int _i, int _d): i(_i), d(_d) {}
    bool operator<(const Vertex &V) const{
        return d > V.d;
    }
};
vector<pair<int, int>> adj[100100];
vector<int> val[100100];
bool visited[100100];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for (int i=0;i<M;i++){
        adj[R[i][0]].emplace_back(R[i][1], L[i]);
        adj[R[i][1]].emplace_back(R[i][0], L[i]);
    }

    priority_queue<Vertex> pq;
    for (int i=0;i<K;i++){
        pq.emplace(P[i], 0);
    }
    while(!pq.empty()){
        auto s = pq.top(); pq.pop();
        //printf(" %d %d\n", s.i, s.d);
        if (!s.i) return s.d;
        if (visited[s.i]) continue;
        visited[s.i] = 1;

        for (auto &v:adj[s.i]) if (!visited[v.first]){
            val[v.first].push_back(v.second + s.d);
            sort(val[v.first].begin(), val[v.first].end());

            if (val[v.first].size()>2) val[v.first].pop_back();
            if (val[v.first].size()==2) pq.emplace(v.first, val[v.first][1]);
        }
    }
    exit(1);
}

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