Submission #1219935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219935		SpyrosAliv	악어의 지하 도시 (IOI11_crocodile)	C++20	100 / 100	304 ms	56540 KiB

crocodile

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

const ll INF = 1e18;

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    vector<vector<pair<int, int>>> g(n);
    vector<vector<ll>> best(n, vector<ll>(2, INF));
    vector<ll> dp(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});
    }
    vector<bool> done(n, false);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, 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], next});
            }
        }
    }
    return (int)dp[0];
}

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