제출 #1289136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289136		harryleee	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	290 ms	72944 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){
                swap(dis[v].first, dis[v].second);
                if (dis[v].first != dis[v].second)
                    pq.push({v, dis[v].second});
                dis[v].first = cur_dis + w;
            }
            else if (cur_dis + w < dis[v].second){
                dis[v].second = cur_dis + w;
                pq.push({v, dis[v].second});
            }
        }
    }

    return dis[0].second;
}

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