Submission #988213

#	Time	Username	Problem	Language	Result	Execution time	Memory
988213		BF001	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	430 ms	82088 KiB

crocodile

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

#define NN 100005
#define oo 1e18
#define fi first
#define se second

typedef pair<long long, long long> ii;

int n, m, k, vs[NN];
long long d1[NN], d2[NN];
vector<int> sr;
vector<ii> adj[NN];

int ditra(){
	for (int i = 0; i <= n; i++) d1[i] = d2[i] = oo;
	priority_queue<ii, vector<ii>, greater<ii>> q;
	for (auto x : sr){
		d2[x] = d1[x] = 0;
		q.push({0, x});
	}
	while (!q.empty()){
		int u = q.top().se;
		int du = d2[u];
		q.pop();
		if (vs[u]) continue;
		vs[u] = 1;
		for (auto x : adj[u]){
			int v = x.fi;
			int dv = x.se;
			if (du + dv < d1[v]){
				d2[v] = d1[v];
				d1[v] = du + dv;
				q.push({d2[v], v});
			}
			else if (du + dv < d2[v]){
				d2[v] = du + dv;
				q.push({d2[v], v});
			}
		}
	}
	return (int) d2[0];
}

int travel_plan(int N, int M , int R[][2], int L[], int k, int p[]){
	n = N;
	m = M;
	for (int i = 0; i < m; i++){
		int a = R[i][0], b = R[i][1], c = L[i];
		adj[a].push_back({b, c});
		adj[b].push_back({a, c}); 
	}
	for (int i = 0; i < k; i++){
		sr.push_back(p[i]);
	}
	return ditra();
}

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