153282025-02-18 12:25:23Leventusz09A lehető legkevesebb metróval utazás (40 pont)cpp17Wrong answer 0/40375ms24116 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;
		}
	}

	int o = INT16_MAX;
	vector<int> x;
	for (int i = 0; i < N; i++) {
		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 << endl; 
	for (int& i : x) cout << i + 1 << " ";
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base0/40
1Wrong answer0/01ms820 KiB
2Wrong answer0/08ms1844 KiB
3Wrong answer0/21ms1004 KiB
4Wrong answer0/21ms820 KiB
5Wrong answer0/22ms820 KiB
6Wrong answer0/21ms820 KiB
7Wrong answer0/23ms1076 KiB
8Wrong answer0/23ms1076 KiB
9Wrong answer0/26ms1588 KiB
10Wrong answer0/24ms1332 KiB
11Wrong answer0/23ms1080 KiB
12Wrong answer0/28ms1876 KiB
13Wrong answer0/28ms1844 KiB
14Wrong answer0/28ms2092 KiB
15Wrong answer0/2374ms24116 KiB
16Wrong answer0/2354ms24036 KiB
17Wrong answer0/2375ms24116 KiB
18Wrong answer0/2356ms24096 KiB
19Wrong answer0/26ms1592 KiB
20Wrong answer0/27ms1844 KiB
21Wrong answer0/24ms1332 KiB
22Wrong answer0/28ms1704 KiB