제출 #1242487

#제출 시각아이디문제언어결과실행 시간메모리
1242487altern23Bosses (BOI16_bosses)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll, ll> #define fi first #define sec second #define ld long double const int MAXN = 5e3; const ll INF = 1e18; const int MOD = 998244353; const ld eps = 1e-6; vector<ll> boss[MAXN + 5]; ll dist[MAXN + 5]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; for(;tc--;){ ll N; cin >> N; for(int i = 1; i <= N; i++){ ll K; cin >> K; for(int j = 1; j <= K; j++){ ll x; cin >> x; boss[x].push_back(i); } } ll ans = INF; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ dist[j] = INF; } queue<ll> q; dist[i] = 0; q.push(i); for(;!q.empty();){ auto x = q.front(); q.pop(); for(auto nxt : boss[x]){ if(dist[nxt] == INF){ dist[nxt] = dist[x] + 1; q.push(nxt); } } } ll MX = -INF; for(int j = 1; j <= N; j++){ MX = max(MX, dist[j]); } if(MX == INF) continue; ll cur = N; for(int j = 1; j <= N; j++){ cur += (MX - dist[j]); } ans = min(ans, cur); } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...