Submission #1286976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286976		MinhKien	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1 ms	332 KiB

crocodile

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define ll long long
#define li pair <ll, int>
#define fi first
#define se second

const int N = 1e5 + 10;
// const int M = 1e6 + 10;
const ll INF = 1e18;

// int n, m, r[M][2], l[M], k, p[N];
ll dis[N][2];
vector <li> v[N];
priority_queue < li, vector <li>, greater <li> > q;

bool opt(int u, ll val) {
    if (dis[u][0] > val) {
        dis[u][1] = dis[u][0];
        dis[u][0] = val;
        if (dis[u][1] != INF) return true;
        return false;
    }

    if (dis[u][1] > val) {
        dis[u][1] = val;
        return true;
    }

    return false;
}

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

    for (int i = 0; i < N; ++i) {
        dis[i][0] = dis[i][1] = INF;
    }

    for (int i = 1; i <= K; ++i) {
        dis[P[i]][0] = dis[P[i]][1] = 0;
        q.push(li(0, P[i]));
    }

    while (!q.empty()) {
        li p = q.top(); q.pop();
        ll w = p.fi;
        int u = p.se;

        if (u == 0) return w;
        if (w > dis[u][1]) continue;

        for (li z: v[u]) {
            if (opt(z.se, w + z.fi)) {
                q.push(li(dis[z.se][1], z.se));
            }
        }
    }

    return INF;
}

// int main() {
//     freopen("input.txt", "r", stdin);

//     cin.tie(0); cout.tie(0);
//     ios_base::sync_with_stdio(false);

//     cin >> n >> m;
//     for (int i = 1; i <= m; ++i) {
//         cin >> r[i][0] >> r[i][1];
//     }

//     for (int i = 1; i <= m; ++i) cin >> l[i];

//     cin >> k;
//     for (int i = 1; i <= k; ++i) cin >> p[i];

//     cout << travel_plan(n, m, r, l, k, p);

//     return 0;
// }

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