Submission #426070

#	Time	Username	Problem	Language	Result	Execution time	Memory
426070		Mounir	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1239 ms	74324 KiB

crocodile

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

const int N_NOEUDS = 1e6, OO = 1e9;
int dMin[N_NOEUDS][2];
bool vu[N_NOEUDS];

struct Noeud {
	int noeud, dist;

	bool operator < (const Noeud &autre) const {
		if (dist != autre.dist)
			return dist > autre.dist;
		return noeud < autre.noeud;
	}
};

vector<pii> aretes[N_NOEUDS];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int iArete = 0; iArete < M; ++iArete){
		int noeud = R[iArete][0], voisin = R[iArete][1], poids = L[iArete];
		aretes[noeud].pb({voisin, poids});
		aretes[voisin].pb({noeud, poids});
	}

	for (int noeud = 0; noeud < N; ++noeud)
		dMin[noeud][0] = dMin[noeud][1] = OO;

	priority_queue<Noeud> pq;
	for (int iSource = 0; iSource < K; ++iSource){
		int source = P[iSource];
	//	cout << "source " << source << endl;
		dMin[source][0] = dMin[source][1] = 0;
		pq.push({source, 0});
	}

	while (!pq.empty()){
		int noeud = pq.top().noeud, dist = pq.top().dist;
		pq.pop();
		if (vu[noeud]) continue;
		vu[noeud] = true;

		//cout << "pq " << noeud << " " << dist << endl;
		for (pii arete : aretes[noeud]){
			int voisin = arete.first, poids = arete.second, tot = dist + poids;
			dMin[voisin][1] = min(dMin[voisin][1], tot);
			if (dMin[voisin][1] < dMin[voisin][0])
				swap(dMin[voisin][1], dMin[voisin][0]);
			pq.push({voisin, dMin[voisin][1]});
		}
	}

	return dMin[0][1];
}

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