제출 #1315174

#제출 시각아이디문제언어결과실행 시간메모리
1315174BigBadBullyBosses (BOI16_bosses)C++20
100 / 100
687 ms948 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define ff first #define ss second #define tri array<int,3> const int inf = 1e18; const int mod = 1e9+7; const int mxn = 1e6 + 1; int exp(int x, int n) { int res = 1; for (; n > 0; res = (n % 2 ? res * x % mod : res), x = x * x % mod, n /= 2) ; return res; } int inv(int x) { return exp(x, mod - 2); } void solve() { int n; cin >> n; vector<vector<int>> graph(n); for(int i = 0; i < n; i++) { int sz; cin >> sz; while(sz--) { int a; cin >> a; graph[--a].push_back(i); } } int mini = inf; for(int rt = 0;rt < n; rt++) { queue<pii> bfs; vector<vector<int>> tree(n); vector<int> vis(n,0); bfs.push({rt,rt}); vector<int> dp(n,inf); dp[rt] = 1; while(bfs.size()) { pii cur =bfs.front(); bfs.pop(); if(vis[cur.ff])continue; vis[cur.ff] = 1; for(int a : graph[cur.ff]) bfs.push({a,cur.ff}),dp[a]=min(dp[a],dp[cur.ff]+1); } int sum = 0; for(int i = 0; i < n; i++) { if(sum>inf) break; sum+=dp[i]; } mini =min(mini,sum); } cout << mini << '\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0)); int t = 1; //cin >>t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...