Submission #381654

#	Time	Username	Problem	Language	Result	Execution time	Memory
381654		BlancaHM	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	7 ms	492 KiB

crocodile

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <unordered_set>
#include "crocodile.h"
using namespace std;

vector<vector<pair<int, int>>> adj;
//vector<int> dist;
unordered_set<int> dest;
vector<int> DP;

int dfs(int u, int par) {
	if (DP[u] != -1)
		return DP[u];
	if (dest.find(u) != dest.end())
		return DP[u] = 0;
	int shortest_child = INT_MAX, second_shortest = INT_MAX;
	for (auto curP: adj[u]) {
		if (curP.first == par)
			continue;
		int ans = dfs(curP.first, u) + curP.second;
		if (ans < shortest_child)
			shortest_child = ans;
		else if (ans < second_shortest)
			second_shortest = ans;
	}
	return DP[u] = second_shortest;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	// run Dijkstra with end vertices as sources

	adj.assign(N, vector<pair<int, int>>());
	for (int i = 0; i < M; i++) {
		adj[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		adj[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}

	/*
	dist.assign(N, INT_MAX);
	priority_queue<pair<int, int>> pq; // {dist, node}
	for (int i = 0; i < K; i++) {
		pq.push(make_pair(0, P[i]));
		dist[P[i]] = 0;
	}

	while(!pq.empty()) {
		int node = pq.top().second();
		int cost = -pq.top().first();
		pq.pop();
		if (dist[node] < cost)
			continue;
		for (auto curP: adj[node]) {
			if (dist[node] + curP.second < dist[curP.first]) {
				dist[curP.first] = dist[node] + curP.second;
				pq.push(make_pair(-dist[curP.first], curP.first));
			}
		}
	}*/

	// find the answer recursively
	return dfs(0, -1);
}

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