Submission #1191945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191945		zh_h	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	251 ms	50688 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
    vector<vector<pair<int, int>>> edge(n);
    for (int i = 0; i < m; i ++) {
        edge[r[i][0]].pb({r[i][1], l[i]});
        edge[r[i][1]].pb({r[i][0], l[i]});
    }

    vector<bool> is_exit(n, false);
    for (int i = 0; i < k; i ++) {
        is_exit[p[i]] = true;
    }

    vector<int> visited(n, 0);
    priority_queue<pair<int, int>> q;
    for (int i = 0; i < k; i ++) {
        for (auto [v, w] : edge[p[i]]) {
            q.push({-w, v});
            visited[p[i]] ++;
        }
    }

    int ans = 1e9;
    while (!q.empty()) {
        int w = -q.top().first, v = q.top().second;
        q.pop();


        visited[v] ++;
        if (visited[v] != 2) continue;

        for (auto [new_v, new_w] : edge[v]) {
            if (visited[new_v] < 2) {
                q.push({-(new_w + w), new_v});
            }
        }

        if (v == 0) {
            ans = w;
            break;
        }
    }

    return ans;
}

// int main() {
//     int n, m, k;
//     cin >> n >> m >> k;

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

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

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

//     int result = travel_plan(n, m, r, l, k, p);
//     cout << result << endl;
// }

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