153372025-02-18 14:01:36Leventusz09A lehető legkevesebb metróval utazás (40 pont)cpp17Runtime error 0/40377ms32000 KiB
#include <iostream>
#include <vector>

using namespace std;

struct Stop {
	vector<int> et; // élek ide / innen
	vector<int> ms; // élek metrói
};

bool ty[10000];
Stop ss[10000];
//int  fs[10000];

//int ff(int i, int f, int m, int t, vector<int> &v) {
	/*
	ty[i] = 1;
	if (i == t) return 0;

	int min = INT16_MAX;
	int pb = -1;
	for (int ni = 0; ni < ss[i].et.size(); ni++) {
		int n = ss[i].et[ni];
		if (ty[n]/*n == f*//*) continue;

		int c = ff(n, i, ss[i].ms[ni], t, v);
		if (c != -1 && c < min) {
			if (m == ss[i].ms[ni]) {
				min = c;
			}
			else {
				min = c + 1;
				pb = ss[i].ms[ni];
			}
		}
	}
	if (pb != -1) v.push_back(pb);
	return min;*/
//}

int main() {
	int N, M, Ind, Erk;
	cin >> N >> M >> Ind >> Erk;
	Ind--; Erk--;

	for (int i = 0, n, t; i < N; i++) {
		cin >> n;
		for (int j = 0, ls = -1; j < n; j++) {
			cin >> t;
			t--;
			if (ls != -1) {
				ss[t ].et.push_back(ls);
				ss[ls].et.push_back( t);
				ss[t ].ms.push_back( i);
				ss[ls].ms.push_back( i);
			}
			ls = t;
		}
	}

	vector<int> Q;
	int si = 0;
	Q.push_back(Ind);
	int mins [N];
	for (int& i : mins) i = INT32_MAX;
	int minms[N];
	int lss  [N];

	mins[Ind] = 0;
	minms[Ind] = 2;
	
	while (si < Q.size()) {
		ty[Q[si]] = 1;
		int cs = Q[si];
		for (int i = 0; i < ss[cs].et.size(); i++) {
			int n = ss[cs].et[i];
			if (!ty[n]) Q.push_back(n);

			if (mins[n] > mins[cs] + (int)(minms[cs] != ss[cs].ms[i])){
				mins[n] = mins[cs] + (int)(minms[cs] != ss[cs].ms[i]);
				minms[n] = ss[cs].ms[i];
				lss[n] = cs;
			}
		}
		Q[si++] = NULL;
		//si++;
	}

	cout << mins[Erk] << endl;
	vector<int> o;
	int ls = Erk;
	int lsls = -1;
	while (ls != Ind) {
		if (lsls != -1) {
			if (minms[ls] != minms[lsls]) {
				o.push_back(minms[ls]);
			}
		}
		else {
			o.push_back(minms[ls]);
		}
		lsls = ls;
		ls = lss[ls];
	}
	int i = o.size();
	while(i--) cout << o[i] + 1 << " ";
	return 0;














	/*
	int o = INT16_MAX;
	vector<int> x;
	for (int i = 0; i < N; i++) {
		if (find(ss[Ind].ms.begin(), ss[Ind].ms.end(), i) == ss[Ind].ms.end()) continue;
		for (int j = 0; j < M; j++) ty[i] = 0;
		vector<int> tx = { i };
		int c = ff(Ind, -1, i, Erk, tx);
		if (c < o) x = tx, o = c;
	}

	cout << o + 1 << endl; 
	for (int& i : x) cout << i + 1 << " ";
	return 0;*/
}
/*
3 12 10 8
6 1 2 3 4 5 6
6 4 5 6 7 8 9
5 3 10 11 12 7



*/
SubtaskSumTestVerdictTimeMemory
base0/40
1Runtime error0/02ms820 KiB
2Runtime error0/07ms1332 KiB
3Runtime error0/22ms820 KiB
4Runtime error0/22ms1076 KiB
5Runtime error0/22ms820 KiB
6Runtime error0/21ms824 KiB
7Runtime error0/283ms32000 KiB
8Runtime error0/23ms1268 KiB
9Runtime error0/24ms1268 KiB
10Runtime error0/24ms1080 KiB
11Runtime error0/287ms32000 KiB
12Runtime error0/28ms1588 KiB
13Runtime error0/28ms1588 KiB
14Runtime error0/27ms1588 KiB
15Runtime error0/2360ms23604 KiB
16Runtime error0/2377ms23580 KiB
17Runtime error0/2358ms23608 KiB
18Runtime error0/2375ms23604 KiB
19Runtime error0/24ms1332 KiB
20Runtime error0/27ms1332 KiB
21Runtime error0/287ms32000 KiB
22Runtime error0/27ms1336 KiB