제출 #755286

#제출 시각아이디문제언어결과실행 시간메모리
755286kirakaminski968Bosses (BOI16_bosses)C++17
67 / 100
1577 ms596 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int MAXN = 5005; const int INF = 1e9; vector<int> adj[MAXN]; int N; ll bfs(int src){ vector<int> depth(N+1,INF); priority_queue<pair<int,int>> pq; pq.push({1,src}); depth[src] = 1; while(!pq.empty()){ int d = pq.top().first, u = pq.top().second; pq.pop(); for(auto v : adj[u]){ if(d+1 < depth[v]){ depth[v] = d+1; pq.push({depth[v],v}); } } } ll ans = 0; bool good = true; for(int i = 1;i<=N;++i){ if(depth[i] == INF){ good = false; break; } ans += depth[i]; } if(!good) return INF; return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i = 1;i<=N;++i){ int K; cin >> K; for(int j = 1;j<=K;++j){ int a; cin >> a; adj[a].push_back(i); } } ll minn = INF; for(int i = 1;i<=N;++i){ minn = min(minn,bfs(i)); } cout << minn << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...