254042026-02-19 20:10:15lorantbA lehető legkevesebb metróval utazás (40 pont)cpp17Runtime error 32/40472ms32000 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,m,x,y; cin >>n>>m>>x>>y;
	vector<set<int>> a(m+1);
	vector<vector<int>> v(n+1);
	vector<int> dist(m+1,-1);
	vector<bool> used(n+1);
	vector<vector<int>> ut(m+1, vector<int>(2));
	vector<int> ans;
	dist[x] = 0;
	for(int i = 1; i <= n; i++) {
		int b; cin >> b;
		v[i].assign(b,0);
		for(int j = 0; j < b; j++) {
			cin >> v[i][j];
			a[v[i][j]].insert(i);
		}
	}
	queue<int> q;
	q.push(x);
	while(q.size() != 0) {
		int u = q.front(); q.pop();
		for(int i : a[u]) {
			if(used[i] == false) {
				used[i] = true;
				for(int j : v[i]) {
					if(dist[j] == -1) {
						dist[j] = dist[u] + 1;
						ut[j][0] = u;
						ut[j][1] = i;
						q.push(j);
					}
				}
			}
		}
	}
	if(dist[y] == -1) cout << -1;
	else {
		int z = y;
		while(z != x) {
			ans.push_back(ut[z][1]);
			z = ut[z][0];
		}
		reverse(begin(ans), end(ans));
		cout << dist[y] <<endl;
		for(int i : ans) cout << i << " ";

	}
}
SubtaskSumTestVerdictTimeMemory
base32/40
1Accepted0/01ms508 KiB
2Accepted0/08ms2100 KiB
3Accepted2/21ms508 KiB
4Accepted2/22ms316 KiB
5Accepted2/21ms564 KiB
6Accepted2/21ms316 KiB
7Accepted2/23ms820 KiB
8Accepted2/23ms820 KiB
9Accepted2/26ms1400 KiB
10Accepted2/24ms1076 KiB
11Accepted2/22ms564 KiB
12Accepted2/28ms2192 KiB
13Accepted2/28ms2232 KiB
14Accepted2/27ms1888 KiB
15Runtime error0/2432ms32000 KiB
16Runtime error0/2442ms32000 KiB
17Runtime error0/2467ms32000 KiB
18Runtime error0/2472ms32000 KiB
19Accepted2/24ms1332 KiB
20Accepted2/27ms1864 KiB
21Accepted2/24ms1084 KiB
22Accepted2/28ms2100 KiB