Submission #392924

#	Time	Username	Problem	Language	Result	Execution time	Memory
392924		Aryan_Raina	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	4 ms	332 KiB

crocodile

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

#define ar array
#define ll long long
const ll INF = 1e15;
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
	vector<ar<ll,2>> g[n];

	for (ll 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<ll> d1(n, INF), d2(n, INF);
	priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq;
	for (ll i = 0; i < k; i++) pq.push({d1[P[i]] = d2[P[i]] = 0, P[i]});

	while (!pq.empty()) {
		ll u = pq.top()[1], dist = pq.top()[0]; pq.pop();
		for (auto v : g[u]) {
			if (dist + v[0] < d1[v[1]]) d2[v[1]] = d1[v[1]], d1[v[1]] = dist + v[0];
			else if (dist + v[0] < d2[v[1]]) d2[v[1]] = dist + v[0];
			else continue;
			if (d2[v[1]] <= INF/2) pq.push({d2[v[1]], v[1]});
		}
	}
	return d2[0];
}

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