Submission #911266

#	Time	Username	Problem	Language	Result	Execution time	Memory
911266		codefox	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	707 ms	76984 KiB

crocodile

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

#define pii pair<int, int>

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    vector<vector<pii>> graph(N);
    vector<int> alt(N, 0);
    vector<int> low(N, 1e9);
    for (int i = 0; i < M; i++)
    {
        graph[R[i][0]].push_back({R[i][1], L[i]});
        graph[R[i][1]].push_back({R[i][0], L[i]});
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 0; i < K; i++)
    {
        pq.push({0, P[i]});
        alt[P[i]]=1;
    }
    
    while(pq.size())
    {
        int i, d;
        tie(d, i) = pq.top();
        pq.pop();
        if (!alt[i])
        {
            alt[i]=1;
            continue;
        }
        if (low[i]!=1e9) continue;
        low[i] = d;
        for (pii ele:graph[i])
        {
            pq.push({d+ele.second, ele.first});
        }
    }
    return low[0];
}

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