153292025-02-18 12:26:09Leventusz09A lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 1/40375ms24028 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 + 1 << endl; 
	for (int& i : x) cout << i + 1 << " ";
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base1/40
1Elfogadva0/01ms1012 KiB
2Hibás válasz0/08ms1844 KiB
3Hibás válasz0/21ms820 KiB
4Részben helyes1/21ms824 KiB
5Hibás válasz0/22ms856 KiB
6Hibás válasz0/21ms820 KiB
7Hibás válasz0/23ms1076 KiB
8Hibás válasz0/23ms1080 KiB
9Hibás válasz0/26ms1728 KiB
10Hibás válasz0/24ms1172 KiB
11Hibás válasz0/23ms1076 KiB
12Hibás válasz0/28ms1820 KiB
13Hibás válasz0/28ms1904 KiB
14Hibás válasz0/28ms2156 KiB
15Hibás válasz0/2374ms24028 KiB
16Hibás válasz0/2356ms23976 KiB
17Hibás válasz0/2356ms23976 KiB
18Hibás válasz0/2375ms23984 KiB
19Hibás válasz0/26ms1588 KiB
20Hibás válasz0/28ms2036 KiB
21Hibás válasz0/24ms1332 KiB
22Hibás válasz0/28ms1588 KiB