Submission #1047918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047918		inkvizytor	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	354 ms	103808 KiB

crocodile

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

#define ll long long
#define pli pair<ll, int>

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    vector<vector<pli>> g (N);
    for (int i = 0; i < M; i++) {
        g[R[i][0]].push_back({L[i], R[i][1]});
        g[R[i][1]].push_back({L[i], R[i][0]});
    }
    vector<bool> odw (N, 0);
    vector<ll> d (N, -1);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for (int i = 0; i < K; i++) {
        d[P[i]] = 0;
        pq.push({(ll)0, P[i]});
    }
    vector<ll> score (N, 0);
    while(!pq.empty()) {
        pli x = pq.top(); pq.pop();
        if (odw[x.second]) continue;
        odw[x.second] = 1;
        score[x.second] = x.first;
        for (pli i : g[x.second]) {
            if (odw[i.second]) {
                continue;
            }
            ll l = x.first+i.first;
            if (d[i.second] == -1) {
                d[i.second] = l;
            }
            else {
                pq.push({max(d[i.second], l), i.second});
                d[i.second] = min(d[i.second], l);
            }
        }
    }
    return score[0];
}

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