제출 #1289131

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

crocodile

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)9e18;

ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    vector<vector<pair<int,ll>>> adj(N);
    for(int i=0;i<M;i++){
        int u = R[i][0];
        int v = R[i][1];
        ll w = L[i];
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    // best1[u] = smallest candidate = min_{neighbor x} (L(u,x) + T_x)
    // best2[u] = second smallest candidate -> T_u = best2[u]
    vector<ll> best1(N, INF), best2(N, INF);

    // min-heap of (candidateDistance, node) ordered by candidateDistance
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

    // exits: T_exit = 0. We treat that by pushing candidate 0 for the exit itself
    for(int i=0;i<K;i++){
        int u = P[i];
        // push a candidate "0" coming from the exit concept
        // we set both best1 and best2 to 0 so that edges adjacent to exit
        // will see L + 0 as candidates.
        if (best1[u] > 0) {
            best2[u] = best1[u];
            best1[u] = 0;
            pq.push({best1[u], u});
        } else if (best2[u] > 0) {
            best2[u] = 0;
            pq.push({best2[u], u});
        }
    }

    // Note: we will propagate candidates: when we pop (d,u) equal to best2[u] (the second smallest),
    // we relax neighbors v with candidate = d + L(u,v).
    while(!pq.empty()){
        auto [cur, u] = pq.top(); pq.pop();
        // we only process when cur equals best2[u] (we want process nodes whose second-best settled)
        if (cur != best2[u]) continue;

        for(auto [v, w] : adj[u]){
            ll cand = cur + w; // L(v,u) + T_u (we popped T_u as best2[u] = cur)
            // Insert cand into v's two-best structure
            if (cand < best1[v]){
                best2[v] = best1[v];
                best1[v] = cand;
                // whenever best2 improved (could be INF->value or decreased), push it
                if (best2[v] < INF) pq.push({best2[v], v});
            } else if (cand < best2[v]){
                best2[v] = cand;
                if (best2[v] < INF) pq.push({best2[v], v});
            }
        }
    }

    // The answer is T_0 = best2[0]
    return best2[0];
}

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