Submission #386593

#	Time	Username	Problem	Language	Result	Execution time	Memory
386593		Kepha	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	611 ms	47076 KiB

crocodile

// IOI 2011 crocodile
#include <bits/stdc++.h>
#define MX 100000
using namespace std;

int N, M, K;
vector<pair<int, int> > edges[MX + 1];
int dist1[MX + 1], dist2[MX + 1];
bool visited[MX + 1];
priority_queue<pair<int, int> > q;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < M; i++) {
        int a = R[i][0], b = R[i][1], c = L[i];
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }

	memset(dist1, 0x3f, sizeof(dist1));
    memset(dist2, 0x3f, sizeof(dist2));

    for (int i = 0; i < K; i++) {
        int x = P[i];
        dist1[x] = dist2[x] = 0;
        q.push({0, x});
    }

    while (q.size()) {
        int node = q.top().second;
        q.pop();

        if (visited[node]) continue;
        visited[node] = true;

        for (auto& edge : edges[node]) {
            if (dist2[node] + edge.second < dist1[edge.first]) {
                dist2[edge.first] = dist1[edge.first];
                dist1[edge.first] = dist2[node] + edge.second;
                q.push({-dist2[edge.first], edge.first});
            }
            else if (dist2[node] + edge.second < dist2[edge.first]) {
                dist2[edge.first] = dist2[node] + edge.second;
                q.push({-dist2[edge.first], edge.first});
            }
        }
    }

  	return dist2[0];
}

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