제출 #866470

#제출 시각아이디문제언어결과실행 시간메모리
866470Irate경주 (Race) (IOI11_race)C++14
9 / 100
3085 ms17812 KiB
#include<bits/stdc++.h> #include "race.h" using namespace std; const int mxN = 2e5 + 3; vector<pair<int, int>>G[mxN]; long long depth[mxN], length[mxN]; int K; void dfs(int node, int par){ for(pair<int, int>& v : G[node]){ if(v.first != par){ depth[v.first] = depth[node] + 1; length[v.first] = length[node] + v.second; if(length[v.first] > K)return; dfs(v.first, node); } } } int best_path(int n, int k, int H[][2], int L[]){ K = k; for(int i = 0;i < n - 1;++i){ int u = H[i][0], v = H[i][1]; G[u].push_back({v, L[i]}); G[v].push_back({u, L[i]}); } long long mn = 1e18; for(int i = 0;i < n;++i){ dfs(i, i); for(int j = 0;j < n;++j){ if(length[j] == k){ mn = min(mn, depth[j]); } } for(int i = 0;i < n;++i){ depth[i] = 0; length[i] = 0; } } if(mn == 1e18)return -1; return mn; } // int main() // { // ios_base::sync_with_stdio(0); // cin.tie(0); // int n; // cin >> n >> K; // int H[n - 1][2], L[n - 1]; // for(int i = 0;i < n - 1;++i){ // cin >> H[i][0] >> H[i][1] >> L[i]; // } // cout << best_path(n, K, H, L); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...