제출 #159458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159458		a_player	Bosses (BOI16_bosses)	C++14	100 / 100	1012 ms	676 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

vector<int> grafo[5001];
int val[5001];
int v[5001];
queue<int> q;
int N;
int fast(){
  int r=0;
  char ch=getchar();
  while(ch<'0' or ch>'9')ch=getchar();
  r=ch-'0';
  ch=getchar();
  while(ch>='0'&&ch<='9'){
    r=(r<<1)+(r<<3)+ch-'0';
    ch=getchar();
  }
  return r;
}

int bfs(int in){
    memset(v,0,sizeof(v));
    memset(val,0,sizeof(val));
    int s=0;
    q.push(in);
    v[in]=1;
    val[in]=1;
    while(!q.empty()){
      int co=q.front();
      q.pop();
      s+=val[co];
      for(int x:grafo[co]){
        if(!v[x]){
          val[x]=val[co]+1;
          v[x]=1;
          q.push(x);
        }
      }
    }
    for(int i=0;i<N;i++)if(!v[i])return (int)1e9;
    return s;

}

int main(){
  N=fast();
  for(int i=0;i<N;i++){
    int n;
    n=fast();
    for(int j=0;j<n;j++){
      int a;
      a=fast();
      grafo[a-1].push_back(i);
    }
  }
  int mini=bfs(0);
  for(int i=1;i<N;i++){
    mini=min(mini,bfs(i));
  }
  cout<<mini;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33