제출 #1313039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313039		ChottuF	악어의 지하 도시 (IOI11_crocodile)	C++20	89 / 100	328 ms	46840 KiB

crocodile

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


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<pair<int,int>> adj[N];
    for (int i = 0; i<M; i++){
        int a = R[i][0];
        int b = R[i][1];
        int w = L[i];
        adj[a].push_back({b,w});
        adj[b].push_back({a,w});
    }
    vector<int> bst(N,1e9), scd(N, 1e9);

    priority_queue<pair<int,int>> pq; //-dist, node
    for (int i = 0; i<K; i++){
        int x = P[i];
        pq.push({0LL,x});
        bst[x] = 0;
        scd[x] = 0;
    }
    
    while (!pq.empty()){
        auto u = pq.top(); pq.pop();
        auto [dist, node] = u;
        dist = -dist;
        if (dist > scd[node]) continue;
        for (auto e : adj[node]){
            auto [a, w] = e;
            int vl = w + dist;
            if (vl < bst[a]){
                scd[a] = bst[a];
                bst[a] = vl;
                pq.push({-scd[a],a});
            }
            else if (vl >= bst[a] && vl < scd[a]){
                scd[a] = vl;
                pq.push({-scd[a],a});
            }
        }
    }
    return scd[0];
}

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