제출 #1144514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144514		zhasyn	경주 (Race) (IOI11_race)	C++20	0 / 100	1 ms	2628 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pll pair <ll, ll>
const ll N = 1e5 + 100;
vector <pll> q[N];
int k, ans = INT_MAX;
void dfs(int v, int pred, int sum, int cnt){
	if(sum > k) return;
	if(sum == k){
		ans = min(ans, cnt);
		return;
	}
	for(auto u : q[v]){
		if(u.F == pred) continue;
		dfs(u.F, v, sum + u.S, cnt + 1);
	}
}
int best_path(int n, int gk, int h[][2], int l[]){
	k = gk;
  for(int i = 1; i <= n; i++){
	q[h[i][0]].pb({h[i][1], l[i]});
	q[h[i][1]].pb({h[i][0], l[i]});
  }
  for(int i = 1; i <= n; i++){
  	dfs(i, -1, 0, 0);
  }
  return ans;
}


// int main(){
	// vector <int> s;
	// int n;
	// cin >> n;
	// for(int i = 0, x; i < n; i++){
		// cin >> x;
		// s.pb(x);
	// }
	// return 0;
// }

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