# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1000754 | 2024-06-18T08:22:15 Z | nomuluun | Race (IOI11_race) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll N, K; ll H[200005][2]; ll L[200005]; bool vis[200005]={0}; vector<pair<int,int>>v[200005]; ll mi=INT_MAX; void dfs(ll q, ll dis, ll hi){ int m=v[q].size(); if(dis==K){ mi=min(mi,hi); } for(int i=0; i<m; i++){ int k=v[q][i].first; ll cost=v[q][i].second; if(!vis[k]){ vis[k]=1; dfs(k,dis+cost,hi+1); } } } int best_path(ll N, ll K, ll H[200005][5], ll L[200005]){ for(int i=0; i<=N-1; i++){ for(int i=0; i<N; i++){ vis[i]=0; } vis[i]=1; dfs(i,0,0); //ehleh oroi distance highway } if(mi==INT_MAX)return -1; else return mi; } int main(){ cin>>N>>K; for(int i=0; i<N-1; i++){ cin>>H[i][0]>>H[i][1]>>L[i]; } for(int i=0; i<N-1; i++){ v[H[i][0]].push_back({H[i][1], L[i]}); v[H[i][1]].push_back({H[i][0], L[i]}); } cout<<best_path(N,K,H,L); }