제출 #971738

#제출 시각아이디문제언어결과실행 시간메모리
971738tnknguyen_경주 (Race) (IOI11_race)C++14
21 / 100
3043 ms15708 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define pii pair<int, int> //#define int long long const int MX = 2e5 + 5; vector<pii> gr[MX]; void dfs(int u, int p, int sum, int cnt,int &ans, const int &k){ if(sum > k){ return; } if(sum == k){ ans = min(ans, cnt); } for(pii e : gr[u]){ int v, c; tie(v, c) = e; if(v != p){ dfs(v, u, sum + c, cnt + 1, ans, k); } } } int best_path(int N, int K, int H[][2], int L[]){ int n = N; for(int i=0; i<n-1; ++i){ int u = H[i][0], v = H[i][1], c = L[i]; ++u, ++v; gr[u].push_back({v, c}); gr[v].push_back({u, c}); } int ans = 1e9; for(int i=1; i<=n; ++i){ dfs(i, 0, 0, 0, ans, K); } return (ans == 1e9 ? -1 : ans); } // int32_t main() { // ios_base::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); // freopen("main.inp","r",stdin); // freopen("main.out","w",stdout); // int n, k; // int h[20][2], l[20]; // cin>>n>>k; // for(int i=0; i<n-1; ++i){ // cin>>h[i][0]>>h[i][1]>>l[i]; // } // cout<<best_path(n, k, h, l); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...