# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1000780 | 2024-06-18T08:39:19 Z | nomuluun | Race (IOI11_race) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; bool vis[200005]={0}; vector<pair<int,int>>v[200005]; ll mi=INT_MAX; void dfs(int q, int dis, int hi, int ka){ int m=v[q].size(); if(dis==ka){ if(hi<mi)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(int N, int K, int H[][2], int L[]){ 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]}); } 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,K); //ehleh oroi distance highway } if(mi==INT_MAX)return -1; else return mi; }