91722024-02-16 19:27:23UVinceA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40157ms45124 KiB
// Source: https://usaco.guide/general/io

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

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m,start,end;
	cin>>n>>m>>start>>end;
	vector<vector<pair<int,int>>> adj(n+m);
	for (int i=0;i<n;i++){
		int ai;
		cin>>ai;
		for (int j=0; j<ai; j++) {
			int a;
			cin>>a;
			a--;
			adj[a].push_back({m+i,1});
			adj[m+i].push_back({a,0});
		}
	}
	start--;
	end--;
	deque<int> dq;
	vector<int> dist(n+m, INT_MAX);
	vector<int> parent(n+m);
	dq.push_back(start);
	dist[start]=0;
	parent[start]=-1;

	while (!dq.empty()){
		int v = dq.front();
		dq.pop_front();

		for (auto [to,dst] : adj[v]){
			
			if (dist[to]==INT_MAX){
				dist[to]=dist[v]+dst;
				parent[to]=v;
				if (dst){
					dq.push_back(to);
				}
				else {
					dq.push_front(to);
				}
			}
		}
	}
	if (dist[end]==INT_MAX){
		cout<<"-1";
		return 0;
	}

	cout<<dist[end]<<"\n";
	vector<int> ans;
	while (end!=-1){
		if (end>=m){
			ans.push_back(end-m);
		}
		end=parent[end];
	}
	reverse(ans.begin(),ans.end());
	for (int i : ans) cout<<i+1<<" ";
}