Submission #44764338

---

Source Code Expand

// Problem: E - Prerequisites
// Contest: AtCoder - KEYENCE Programming Contest 2023 Summer（AtCoder Beginner Contest 315）
// URL: https://atcoder.jp/contests/abc315/tasks/abc315_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define double long double
#define superSLOW ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TxtIO  freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
const int mod=1e9+7;
const int inf=1e18;
using namespace std;

void dijkstra(vector<vector<pair<int,int>>> &g , vector<int> &dis , int node){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,node});
	dis[node]=0;
	while(!pq.empty()){
		auto u=pq.top();pq.pop();
		int node=u.ss;
		int d=u.ff;
		if(dis[node]<d)continue;
		dis[node]=d;
		for(auto ch:g[node]){
			if(dis[ch.ff]>(dis[node]+ch.ss)){
				dis[ch.ff]=dis[node]+ch.ss;
				pq.push({dis[ch.ff],ch.ff});
			}
		}
	}
}

int32_t main() {
	// your code goes hereTxtIO;
	superSLOW;
	int n;cin>>n;
	vector<vector<pii>>g(n+1);
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		while(x--){
			int y;cin>>y;
			g[i].pb({y,-1});
		}
	}
	
	vector<int>dis(n+1,inf);
	dijkstra(g,dis,1);
	vector<pii>ans;
	for(int i=1;i<=n;i++){
		ans.pb({dis[i],i});
	}
	sort(ans.begin(),ans.end());
	for(int i=0;i<n;i++){
		if(ans[i].ff==inf or ans[i].ss==1)break;
		cout<<ans[i].ss<<" ";
	}
	cout<<endl;
	return 0;
}

Submission Info

Judge Result