Submission #1043044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043044		allin27x	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	300 ms	97464 KiB

crocodile

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

const int N = 1e5+4;
const int INF = 1e9+2;
vector<pair<int,int>> adj[N];
int ds[N][2];

#define tp tuple<int,int,int>

signed travel_plan(signed n, signed m, signed r[][2], signed l[], signed k, signed p[]){
	for (int i=0; i<m; i++){
		adj[r[i][0]].push_back({r[i][1], l[i]});
		adj[r[i][1]].push_back({r[i][0], l[i]});
	}
	for (int i=0; i<n; i++) ds[i][0]=INF, ds[i][1] = INF;
	for (int i=0; i<k; i++) ds[p[i]][0]=0, ds[p[i]][1] = 0;
	// <second best distance, best distance, node> 
	priority_queue<tp, vector<tp>, greater<tp>> q;
	for (int i=0; i<k; i++) q.push({0,0,p[i]});
	while (!q.empty()){
		auto [b2,b1,u] = q.top(); q.pop();
		if (b2 != ds[u][0] || b1 != ds[u][1]) continue; 
		for (auto [v,w]: adj[u]){
			if (w + b2 < ds[v][1]){
				ds[v][0] = ds[v][1]; ds[v][1] = w + b2;
				q.push({ds[v][0], ds[v][1], v});
			} else if (w + b2 < ds[v][0]){
				ds[v][0] = w+b2;
				q.push({ds[v][0], ds[v][1], v});
			}
		}
	}
	return ds[0][0];

}

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