제출 #849426

#제출 시각아이디문제언어결과실행 시간메모리
849426Mr_Ph경주 (Race) (IOI11_race)C++14
0 / 100
11 ms83804 KiB
#include "race.h" #include<bits/stdc++.h> using namespace std; vector<int>vs; vector<int>vs1; vector<vector<pair<int,int>>>adj; int ans=1e6; int pog=0; int dp[200002][102]; void dfs(int node,int lol,int sum) { vs[node]=true; if(sum>pog) return; if(sum==pog) { ans=min(ans,lol); return; } for(auto i:adj[node]) { if(!vs[i.first]) { // cout<<node<<" "<<i.first<<" "<<i.second<<endl; dfs(i.first,lol+1,sum+i.second); } } } int dfs1(int node,int sum,int p) { if(sum>pog) return 1e6; if(sum==pog) return 0; if(dp[node][sum]!=-1) return dp[node][sum]; int e=1e6; for(auto i:adj[node]) { if(i.first==p) continue; e=min(e,dfs1(i.first,sum+i.second,node)+1); } return dp[node][sum]=e; } int best_path(int n, int k, int h[][2], int l[]) { memset(dp,-1,sizeof dp); pog=k; adj.resize(n+1); vs.resize(n+1); vs1=vs; for(int i=0; i<n-1; i++) { // cout<<h[i][0]<<" "<<h[i][1]<<" "<<l[i]<<endl; adj[h[i][0]].push_back({h[i][1],l[i]}); adj[h[i][1]].push_back({h[i][0],l[i]}); } for(int i=0;i<n;i++) ans=min(ans,dfs1(i,0,-1)); if(ans>=1e6) ans=-1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...