제출 #1324043

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

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    // Grafni qo'shnichilik ro'yxati ko'rinishida saqlash
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }

    // min1 - eng qisqa, min2 - ikkinchi eng qisqa masofa
    vector<ll> min1(N, INF), min2(N, INF);
    vector<bool> visited(N, false);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    // Barcha chiqish xonalarini 0 masofa bilan boshlash
    for (int i = 0; i < K; i++) {
        min1[P[i]] = min2[P[i]] = 0;
        pq.push({0, P[i]});
    }

    while (!pq.empty()) {
        ll d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        // Agar 0-xonaga yetib kelgan bo'lsak, bu eng kichik T bo'ladi
        if (u == 0) return (int)d;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            ll weight = edge.second;
            ll new_dist = d + weight;

            // v xonasi uchun eng yaxshi ikkita masofani yangilash
            if (new_dist < min1[v]) {
                min2[v] = min1[v];
                min1[v] = new_dist;
            } else if (new_dist < min2[v]) {
                min2[v] = new_dist;
            }

            // Agar ikkinchi masofa yangilangan bo'lsa va hali tashrif buyurilmagan bo'lsa
            if (min2[v] != INF && !visited[v]) {
                pq.push({min2[v], v});
            }
        }
    }

    return (int)min2[0];
}

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