제출 #849410

#제출 시각아이디문제언어결과실행 시간메모리
849410Mr_Ph경주 (Race) (IOI11_race)C++14
0 / 100
73 ms169732 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=1e9; int pog=0; int dp[200001][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 1e9; if(sum==pog) return 0; if(dp[node][sum]!=-1) return dp[node][sum]; int e=1e9; for(auto i:adj[node]) { if(i.first==p) continue; e=min(e,dfs1(i.first,sum+i.second,node)+1); } 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]}); } if(n<=20000&&k<=100) { for(int i=0;i<n;i++) ans=min(ans,dfs1(i,0,-1)); } else { for(int i=0; i<n; i++) { vs=vs1; dfs(i,0,0); // cout<<ans<<endl; } } if(ans>=1e9) ans=-1; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int dfs1(int, int, int)':
race.cpp:44:18: warning: control reaches end of non-void function [-Wreturn-type]
   44 |     dp[node][sum]=e;
      |     ~~~~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...