제출 #216368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216368		MODDI	경주 (Race) (IOI11_race)	C++14	0 / 100	11 ms	12032 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vll vector<pll>
#define vii vector<pii>
using namespace std;
vii G[500000];
bool dp[10000][10000];
int K;
void dfs(int at, int path, int passed_cities, int prev){
	if(path > K)
		return;
	for(auto next : G[at]){
		if(next.first == prev)
			continue;
		else{
			dp[next.first][passed_cities] = path + next.second;
			dfs(next.first, path + next.second, passed_cities + 1, at);
		}
	}
}
int best_path(int n, int k, int H[][2], int L[]){
	for(int i = 0; i < n - 1; i++){
		G[H[i][0]].push_back(make_pair(H[i][1], L[i]));
		G[H[i][1]].push_back(make_pair(H[i][0], L[i]));
	}
	dfs(0, 0, 0, -1);
	int best = 1e9;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			best = min(best, j);
		}
	}
	if(best == 1e9)
		return -1;
	return best;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57