제출 #922096

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

race

#include "race.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vi> vv;

const int inf = 1e9, mod = 998244353;

struct gg{
	int ps, dp = 0, sm = 0, pr;
};
int best_path(int n, int k, int h[][2], int l[])
{
	vii g[n+1];
	for(int i = 0; i < n-1; i++){
		g[h[i][0]].pb({h[i][1], l[i]});
		g[h[i][1]].pb({h[i][0], l[i]});
	}
	
	int ans = inf;
	
	for(int i = 1; i <= n; i++){
		queue<gg> q;
		gg o;
		o.ps = i;
		o.dp = 0;
		o.sm = 0;
		o.pr = -1;
		while(!q.empty()){
			gg res = q.front();
			q.pop();
			if(res.sm > k)continue;
			if(res.sm == k){
				ans = min(ans, o.dp);
				continue;
			}
			for(auto [to, cst]:g[res.ps]){
				if(to == res.pr)continue;
				gg nw;
				nw.ps = to;
				nw.pr = res.ps;
				nw.sm = res.sm+cst;
				nw.dp = res.dp+1;
				q.push(nw);
			}
		}
	}
	return (ans == inf?-1:ans);
}

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