Submission #1065900

#TimeUsernameProblemLanguageResultExecution timeMemory
1065900vjudge1Bosses (BOI16_bosses)C++17
100 / 100
518 ms604 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define db double #define ld long double #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define fi first #define se second #define debug(x) cout << #x << " => " << x << "\n" #define all(x) x.begin(),x.end() vector<int> adj[5010]; int ans=1e9; int d[5010]; void bfs(int x,int n) { int cnt=0; memset(d,-1,sizeof(d)); queue<pii> q; q.push({x,1}); d[x]=0; int num=0; while(!q.empty()) { int u=q.front().fi,de=q.front().se; q.pop(); cnt+=de; num++; for(auto i : adj[u]) { if(d[i]==-1) { d[i]=de+1; q.push({i,d[i]}); } } } if(num==n) ans=min(ans,cnt); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n;cin>>n; for(int i=1;i<=n;i++) { int x;cin>>x; while(x--) { int j;cin>>j; adj[j].pb(i); } } for(int i=1;i<=n;i++) bfs(i,n); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...