제출 #1289120

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

crocodile

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;

struct cmp{
    bool operator()(const pair<long long, long long>& a, const pair<long long, long long>& b) const {
        return a.second > b.second;
    }
};

long long travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
    vector<vector<pair<long long, long long>>> adj(n);
    vector<pair<long long, long long>> dis(n);

    for (int i = 0; i < n; ++i) dis[i].first = dis[i].second = inf;

    for (int i = 0; i < m; ++i){
        long long u = R[i][0], v = R[i][1], w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, cmp> pq;
    for (int i = 0; i < k; ++i){
        int u = P[i];
        dis[u].first = dis[u].second = 0;
        pq.push({u, 0});
    }    

    while(!pq.empty()){
        long long u = pq.top().first;
        long long cur_dis = pq.top().second;
        pq.pop();
        if (cur_dis != dis[u].second) continue;
        for (auto [v, w] : adj[u]){
            bool opt = false;
            if (cur_dis + w <= dis[v].first){
                dis[v].second = dis[v].first;
                dis[v].first = cur_dis + w;
                opt = true;
            }
            else if (cur_dis + w < dis[v].second){
                dis[v].second = cur_dis + w;
                opt = true;
            }
            if (opt && dis[v].first != inf && dis[v].second != inf)
                pq.push({v, dis[v].second});
        }
    }

    return dis[0].second;
}

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