#include "race.h" #include <climits> #include <vector> #include <utility> // для pair using namespace std; // Рекурсивный DFS вне best_path void dfs(int v, int p, int length, int edges, int K, vector<vector<pair<int,int>>> &g, int &answer) { if(length == K){ if(edges > 0) // путь хотя бы через одну дорогу answer = min(answer, edges); return; } if(length > K) return; for(size_t i=0;i<g[v].size();i++){ int u = g[v][i].first; int w = g[v][i].second; if(u != p){ dfs(u, v, length + w, edges + 1, K, g, answer); } } } int best_path(int N, int K, int H[][2], int L[]) { vector<vector<pair<int,int>>> g(N); 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])); } int answer = INT_MAX; for(int i=0;i<N;i++){ dfs(i, -1, 0, 0, K, g, answer); } if(answer == INT_MAX) return -1; return answer; }