Submission #1183057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183057		Erick_7314	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	329 ms	62104 KiB

crocodile

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

using namespace std;

typedef long long ll;
typedef pair<ll, int> lli;
typedef priority_queue<lli, vector<lli>, greater<lli>> PQ;

const int MAXN = 100010;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<vector<int>> adj(N);
    vector<vector<int>> len(N);
    vector<int> vis(N, 0);
    ll ans = -1;

    // Construcción del grafo
    for (int i = 0; i < M; i++) {
        int u = R[i][0], v = R[i][1];
        adj[u].push_back(v);
        len[u].push_back(L[i]);
        adj[v].push_back(u);
        len[v].push_back(L[i]);
    }

    // Dijkstra desde cámaras de salida
    PQ pq;
    for (int i = 0; i < K; i++) {
        int x = P[i];
        pq.push({0, x});
        vis[x] = 1;  // 1 = visitado por primera vez
    }

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

        if (!vis[u]) {
            vis[u] = 1;
            continue;
        }
        if (vis[u] == 2) continue;

        if (u == 0) {
            ans = l;
            break;
        }

        vis[u] = 2;
        for (int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i];
            if (vis[v] == 2) continue;
            ll nl = l + len[u][i];
            pq.push({nl, v});
        }
    }

    return (int)ans;
}

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