9172 2024. 02. 16 19:27:23 UVince A lehető legkevesebb metróval utazás (40 pont) cpp17 Elfogadva 40/40 157ms 45124 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<<" ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1828 KiB
2 Elfogadva 0/0 4ms 3484 KiB
3 Elfogadva 2/2 3ms 2228 KiB
4 Elfogadva 2/2 3ms 2444 KiB
5 Elfogadva 2/2 3ms 2868 KiB
6 Elfogadva 2/2 2ms 2740 KiB
7 Elfogadva 2/2 3ms 3056 KiB
8 Elfogadva 2/2 3ms 3240 KiB
9 Elfogadva 2/2 4ms 3608 KiB
10 Elfogadva 2/2 4ms 3548 KiB
11 Elfogadva 2/2 3ms 3312 KiB
12 Elfogadva 2/2 6ms 4412 KiB
13 Elfogadva 2/2 6ms 4664 KiB
14 Elfogadva 2/2 4ms 4944 KiB
15 Elfogadva 2/2 144ms 44316 KiB
16 Elfogadva 2/2 156ms 44132 KiB
17 Elfogadva 2/2 145ms 44056 KiB
18 Elfogadva 2/2 157ms 45124 KiB
19 Elfogadva 2/2 4ms 4804 KiB
20 Elfogadva 2/2 4ms 5392 KiB
21 Elfogadva 2/2 4ms 4720 KiB
22 Elfogadva 2/2 4ms 5580 KiB