제출 #756610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756610		siewjh	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	3 ms	3284 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;
	vis[x] = 1;
	vector<int> res;
	for (auto nxt : adj[x]){
		int nn = nxt.first, nd = nxt.second;
		int nres = min(dfs(nn) + nd, inf);
		res.push_back(nres);
	}
	sort(res.begin(), res.end());
	if (res.size() < 2) return dp[x] = inf;
	else return dp[x] = res[1];
}

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;
	memset(dp, -1, sizeof(dp));
	return dfs(0);
}

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