제출 #1366141

#제출 시각아이디문제언어결과실행 시간메모리
1366141ivazivaBosses (BOI16_bosses)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 5005
#define int long long 

int n;
vector<int> in[MAXN];
vector<pair<int,pair<int,int>>> edges;
int parent[MAXN],siz[MAXN];
queue<pair<int,int>> nodes;bool pos[MAXN];

int get(int node)
{
	if (parent[node]==node) return node;
	return get(parent[node]);
}

bool unite(int node1,int node2)
{
	node1=get(node1),node2=get(node2);
	if (node1==node2) return false;
	if (siz[node1]<siz[node2]) swap(node1,node2);
	parent[node2]=node1;siz[node1]+=siz[node2];return true;
}

int32_t main()
{
	cin>>n;
	for (int node=1;node<=n;node++) 
	{
		int number;cin>>number;
		for (int pos=1;pos<=number;pos++) {int sled;cin>>sled;in[sled].push_back(node);}
	}
	int answer=LLONG_MAX;
	for (int root=1;root<=n;root++)
	{
		edges.clear();for (int node=1;node<=n;node++) {parent[node]=node;siz[node]=1;pos[node]=false;}
		nodes.push({root,2});
		while (!nodes.empty())
		{
			int node=nodes.front().first,cost=nodes.front().second;nodes.pop();pos[node]=true;
			for (int sled:in[node])
			{
				edges.push_back({cost,{node,sled}});
				if (!pos[sled]) nodes.push({sled,cost+1});
			}
		}
		sort(edges.begin(),edges.end());int solution=1;
		for (pair<int,pair<int,int>> edge:edges)
		{
			int cost=edge.first,node1=edge.second.first,node2=edge.second.second;
			if (unite(node1,node2)) solution+=cost;
		}
		answer=min(answer,solution);
    }
    cout<<answer<<endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…