Submission #1243610

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

crocodile

#include <bits/stdc++.h>
#define Longgggg ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define endl '\n'
using namespace std;
#define fi first
#define se second

const ll LINF = (ll) 1e18;
const int mxN = 100005;

ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; ++i) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    // d[u][0] = best, d[u][1] = second best
    vector<array<ll, 2>> d(N, {LINF, LINF});
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    for (int i = 0; i < K; ++i) {
        d[P[i]][0] = 0;
        pq.push({0, P[i]});
    }
    while (!pq.empty()) {
        auto [cost, u] = pq.top(); pq.pop();
        for (auto [v, w] : adj[u]) {
            ll cand = cost + w;
            if (cand < d[v][0]) {
                d[v][1] = d[v][0];
                d[v][0] = cand;
                pq.push({d[v][0], v});
            } else if (cand > d[v][0] && cand < d[v][1]) {
                d[v][1] = cand;
                pq.push({d[v][1], v});
            }
        }
    }
    return d[0][1];
}

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