#include "race.h" #include <vector> #include <climits> #include <algorithm> using namespace std; #define pii pair<int,int> vector<int> dp[105]; vector<int> suf[105]; vector<vector<pii>> g; int ans; 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++){ if(dp[i][v] != INT_MAX) 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++){ if(suf[i][k.first] != INT_MAX){ 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[]){ g.clear(); g.resize(N); ans = INT_MAX; for(int i=0;i<=100;i++){ dp[i].clear(); suf[i].clear(); dp[i].resize(N, INT_MAX); suf[i].resize(N, INT_MAX); } for(int i=0;i<N-1;i++){ g[H[i][0]].push_back({H[i][1], L[i]}); g[H[i][1]].push_back({H[i][0], L[i]}); } dfs(0,-1); // запускаем с вершины 0 for(int i=0;i<N;i++){ ans = min(ans, dp[K][i]); } if(ans == INT_MAX) return -1; return ans; }