Submission #756605

#	Time	Username	Problem	Language	Result	Execution time	Memory
756605		siewjh	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	2 ms	2644 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int inf = 1e9 + 7;
vector<pair<int, int>> adj[MAXN];
int dp[MAXN];
bool vis[MAXN], isexit[MAXN];

int dfs(int x){
	if (isexit[x]) return 0;
	if (dp[x] != -1) return dp[x];
	if (vis[x]) return inf;
	vector<pair<int, int>> res;
	for (auto nxt : res){
		int nn = nxt.first, nd = nxt.second;
		int nres = min(dfs(nn) + nd, inf);
		res.push_back({nres, nn});
	}
	sort(res.begin(), res.end());
	vis[x] = 1;
	if (res.size() < 2) return inf;
	else return res[1].first;
}

int travel_plan(int nodes, int edges, int elist[][2], int elen[], int exits, int exarr[]){
	for (int i = 0; i < edges; i++){
		int a = elist[i][0], b = elist[i][1], d = elen[i];
		adj[a].push_back({b, d});
		adj[b].push_back({a, d});
	}
	for (int i = 0; i < exits; i++) isexit[exarr[i]] = 1;
	return dfs(0);
}

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