Submission #53667

#	Time	Username	Problem	Language	Result	Execution time	Memory
53667		wilwxk	Bosses (BOI16_bosses)	C++17	100 / 100	969 ms	118424 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

const int MAXN=6e3+5;
const long long INF=1e18;
vector<int> g[MAXN];
int dist[MAXN][MAXN];
queue<int> q;
long long resp;
int n;

void bfs(int ori) {
	q.push(ori); dist[ori][ori]=0;
	while(q.size()) {
		int cur=q.front(); q.pop();
		for(auto viz : g[cur]) {
			if(dist[ori][cur]+1<dist[ori][viz]) {
				dist[ori][viz]=dist[ori][cur]+1;
				q.push(viz);
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		int a; scanf("%d", &a);
		while(a--) {
			int b; scanf("%d", &b);
			g[b].push_back(i);
		}
	}
	
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dist[i][j]=MAXN;
	for(int i=1; i<=n; i++) bfs(i);
	resp=INF;
	
	//for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) printf("%d ", dist[i][j]); printf("\n"); }
	
	for(int i=1; i<=n; i++) {
		long long cur=0;
		for(int j=1; j<=n; j++) cur+=(dist[i][j]+1);
		if(cur<resp) resp=cur;
	}
	
	printf("%lld\n", resp);
	
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bosses.cpp:28:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
bosses.cpp:30:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int b; scanf("%d", &b);
           ~~~~~^~~~~~~~~~

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