Submission #1248901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248901		12baater	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	379 ms	58808 KiB

crocodile

#include "crocodile.h"
#include <functional>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>


using namespace std;
typedef long long ll;
const ll INF = 1E15;

int 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++) {
        int a = R[i][0], b = R[i][1], c = L[i];
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }

    vector<int> visited(N);
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<>> pq;
    for (int i = 0; i < K; i++) {
        visited[P[i]] = 1;
        pq.emplace(0, P[i]);
    }

    for (; !pq.empty(); pq.pop()) {
        auto [dist, node] = pq.top();

        if (visited[node] == 0) {
            visited[node] = 1;
            continue;
        }

        if (node == 0) {
            return dist;
        }
        if (visited[node] > 1) continue;
        visited[node]++;

        for (auto [child, cost] : adj[node]) {
            if (visited[child] > 1) continue;
            pq.emplace(dist+cost, child);
        }
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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