91722024-02-16 19:27:23UVinceA lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 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<<" ";
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/03ms1828 KiB
2Accepted0/04ms3484 KiB
3Accepted2/23ms2228 KiB
4Accepted2/23ms2444 KiB
5Accepted2/23ms2868 KiB
6Accepted2/22ms2740 KiB
7Accepted2/23ms3056 KiB
8Accepted2/23ms3240 KiB
9Accepted2/24ms3608 KiB
10Accepted2/24ms3548 KiB
11Accepted2/23ms3312 KiB
12Accepted2/26ms4412 KiB
13Accepted2/26ms4664 KiB
14Accepted2/24ms4944 KiB
15Accepted2/2144ms44316 KiB
16Accepted2/2156ms44132 KiB
17Accepted2/2145ms44056 KiB
18Accepted2/2157ms45124 KiB
19Accepted2/24ms4804 KiB
20Accepted2/24ms5392 KiB
21Accepted2/24ms4720 KiB
22Accepted2/24ms5580 KiB