Submission #1219922

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

crocodile

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll INF = 1e18;
int n, m;
vector<vector<pair<int, int>>> g;
vector<ll> dp;
vector<vector<ll>> best;

int travel_plan(int N, int M, int r[][2], int l[], int k, int p[]) {
    n = N;
    m = M;
    g.clear();
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int u = r[i][0];
        int v = r[i][1];
        int w = l[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dp.assign(n, INF);
    best.assign(n, vector<ll>(2, INF));
    vector<bool> done(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < k; i++) {
        dp[p[i]] = 0;
        best[p[i]][0] = best[p[i]][1] = 0;
        pq.push({0, p[i]});
    }
    while (!pq.empty()) {
        int curr = pq.top().second;
        pq.pop();
        if (done[curr]) continue;
        done[curr] = true;
        dp[curr] = best[curr][1];
        for (auto [next, w]: g[curr]) {
            if (done[next]) continue;
            ll dis = w + dp[curr];
            if (dis < best[next][1]) {
                if (dis <= best[next][0]) {
                    best[next][1] = best[next][0];
                    best[next][0] = dis;
                }
                else best[next][1] = dis;
            }
            pq.push({best[next][1], dis});
        }
    }
    return dp[0];
}

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