Submission #1183047

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

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#include <limits>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

struct Edge {
    int to;
    ll w;
};

struct Node {
    ll val;
    int id;
    bool operator>(const Node &other) const {
        return val > other.val;
    }
};

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

    vector<bool> exitChamber(N, false);
    for (int i = 0; i < K; ++i)
        exitChamber[P[i]] = true;

    vector<ll> f(N, INF), best(N, INF), second(N, INF);
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    for (int i = 0; i < N; ++i) {
        if (exitChamber[i]) {
            f[i] = 0;
            pq.push({0, i});
        }
    }

    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int u = cur.id;
        if (cur.val != f[u]) continue;

        for (auto &edge : adj[u]) {
            int v = edge.to;
            if (exitChamber[v]) continue;

            ll candidate = edge.w + f[u];
            if (candidate < best[v]) {
                second[v] = best[v];
                best[v] = candidate;
            } else if (candidate < second[v] && candidate != best[v]) {
                second[v] = candidate;
            }

            if (second[v] < f[v]) {
                f[v] = second[v];
                pq.push({f[v], v});
            }
        }
    }

    return (int)f[0];
}

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