#include "race.h" #include <vector> #include <climits> #include <algorithm> #include <iostream> using namespace std; #define pii pair<int,int> vector<int> dp[105]; vector<int> suf[105]; vector<vector<pii>> g; int ans = INT_MAX; void dfs(int v,int p){ dp[0][v] = 0; for(auto k : g[v]){ if(k.first != p){ for(int i=0;i<=100-k.second;i++){ dp[i+k.second][k.first] = min(dp[i+k.second][k.first], dp[i][v]+1); } dfs(k.first, v); for(int i=0;i<=100-k.second;i++){ dp[i+k.second][v] = min(dp[i+k.second][v], suf[i][k.first]+1); suf[i+k.second][v] = min(suf[i+k.second][v], suf[i][k.first]+1); } } } suf[0][v] = 0; } int best_path(int N, int K, int H[][2], int L[]){ int n = N; int k = K; int a,b,c; g.resize(n+1); for(int i=0;i<n-1;i++){ a = H[i][0]; b = H[i][1]; c = L[i]; g[a].push_back({b,c}); g[b].push_back({a,c}); } for(int i=0;i<=100;i++){ dp[i].resize(n+1, INT_MAX); suf[i].resize(n+1, INT_MAX); } dfs(1,-1); for(int i=0;i<n;i++){ ans = min(dp[k][i], ans); } if(ans==INT_MAX) return -1; return ans; }