This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MN = 2e5+5;
struct Edge{
int x,d;
Edge(int a, int b){
x = a;
d = b;
}
};
vector<Edge> T[MN];
int DFS(int i, int val, int dis, int r, int K){
if(dis==K) return val;
if(dis>K) return MN;
int res = MN;
for(auto it : T[i]){
if(it.x==r) continue;
res = min(res,DFS(it.x,val+1,dis+it.d,i,K));
}
return res;
}
int best_path(int N, int K, int H[][2], int L[])
{
int ans = N;
for(int i=0; i<N; i++){
T[H[i][0]].push_back(Edge(H[i][1],L[i]));
T[H[1][0]].push_back(Edge(H[i][0],L[i]));
}
for(int i=0; i<N; i++){
ans = min(ans,DFS(i,0,0,i,K));
}
if(ans==N) ans = -1;
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |