# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
975183 | Error404 | Bosses (BOI16_bosses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,int>
const int MAX = 5001;
int color[MAX];
ll dis[MAX];
vector<int>g[MAX];
int n;
ll bfs(int u){
fill(dis+1,dis+1+n, LLONG_MAX);
dis[u] =1;
memset(color,0,sizeof(color));
queue<int>q;
q.push(u);
while(!q.empty()){
int from = q.front();
q.pop();
if(color[from]) continue;
color[from]=1;
for(int to: g[from]){
if(!color[i]){
dis[to]= dis[from]+1;
q.push(to);
}
}
}
ll sum = 0;
for(int i = 1; i <=n; i++) {
sum+= dis[i];
if(dis[i]==LLONG_MAX) return LLONG_MAX;
}
// cout << endl << sum << " "<< u << endl;
// cout << u << " "<< sum << endl;
return sum;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
int temp, k;
for(int i = 1; i <= n; i++){
cin >> temp;
while(temp--){
cin >> k;
g[k].pb(i);
}
}
ll ans= LLONG_MAX;
for(int i= 1; i <= n; i++){
ans = min(bfs(i),ans);
}
cout << ans << endl;
}