153352025-02-18 13:50:52Leventusz09A lehető legkevesebb metróval utazás (40 pont)cpp17Runtime error 4/40589ms32000 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 [10000];
	for (int& i : mins) i = INT32_MAX;
	int minms[10000];
	int lss  [10000];

	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
base4/40
1Accepted0/01ms820 KiB
2Runtime error0/087ms32000 KiB
3Wrong answer0/21ms1004 KiB
4Accepted2/21ms820 KiB
5Accepted2/22ms820 KiB
6Wrong answer0/21ms820 KiB
7Runtime error0/294ms32000 KiB
8Runtime error0/292ms32000 KiB
9Runtime error0/285ms32000 KiB
10Runtime error0/287ms32000 KiB
11Runtime error0/286ms32000 KiB
12Runtime error0/297ms32000 KiB
13Runtime error0/297ms32000 KiB
14Runtime error0/297ms32000 KiB
15Time limit exceeded0/2589ms31860 KiB
16Time limit exceeded0/2574ms32000 KiB
17Time limit exceeded0/2574ms32000 KiB
18Time limit exceeded0/2564ms32000 KiB
19Runtime error0/286ms32000 KiB
20Runtime error0/287ms32000 KiB
21Runtime error0/2100ms32000 KiB
22Runtime error0/289ms32000 KiB