153372025-02-18 14:01:36Leventusz09A lehető legkevesebb metróval utazás (40 pont)cpp17Futási hiba 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



*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/40
1Futási hiba0/02ms820 KiB
2Futási hiba0/07ms1332 KiB
3Futási hiba0/22ms820 KiB
4Futási hiba0/22ms1076 KiB
5Futási hiba0/22ms820 KiB
6Futási hiba0/21ms824 KiB
7Futási hiba0/283ms32000 KiB
8Futási hiba0/23ms1268 KiB
9Futási hiba0/24ms1268 KiB
10Futási hiba0/24ms1080 KiB
11Futási hiba0/287ms32000 KiB
12Futási hiba0/28ms1588 KiB
13Futási hiba0/28ms1588 KiB
14Futási hiba0/27ms1588 KiB
15Futási hiba0/2360ms23604 KiB
16Futási hiba0/2377ms23580 KiB
17Futási hiba0/2358ms23608 KiB
18Futási hiba0/2375ms23604 KiB
19Futási hiba0/24ms1332 KiB
20Futási hiba0/27ms1332 KiB
21Futási hiba0/287ms32000 KiB
22Futási hiba0/27ms1336 KiB