Submission #857878

#	Time	Username	Problem	Language	Result	Execution time	Memory
857878		asdasdqwer	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	397 ms	69272 KiB

crocodile

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

#define pii pair<int, int>
#define pll pair<int64_t, int64_t>

int travel_plan(int n, int m, int R[][2], int L[], int k, int p[]) {
    vector<vector<pii>> g(n);

    for (int i=0;i<m;i++) {
        int a = R[i][0], b = R[i][1];
        int c = L[i];

        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    vector<pll> dist(n, make_pair((int)1e16, (int)1e16));
    for (int i=0;i<k;i++) {
        dist[p[i]] = {0, 0};
    }

    priority_queue<pll> pq;
    for (int i=0;i<n;i++) {
        pq.push({-dist[i].second, i});
    }
    vector<bool> proc(n, false);

    while (!pq.empty()) {
        pii t=pq.top();pq.pop();
        int node=t.second;
        if (proc[node]) continue;
        proc[node] = true;

        for (auto x:g[node]) {
            if (dist[node].second + x.second < dist[x.first].first) {
                dist[x.first].second = dist[x.first].first;
                dist[x.first].first = dist[node].second + x.second;
                pq.push({-dist[x.first].second, x.first});
            }

            else if (dist[node].second + x.second < dist[x.first].second) {
                dist[x.first].second = dist[node].second + x.second;
                pq.push({-dist[x.first].second, x.first});
            }
        }
    }

    return dist[0].second;
}

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