148222025-02-03 14:29:58KateTaylorA lehető legkevesebb metróval utazás (40 pont)cpp17Időlimit túllépés 18/40601ms12596 KiB
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

typedef unordered_set<int> us;

int n, m, beg, arr;
vector<us> conn;
vector<us> edges;
vector<int> sol(201);

void solve(vector<bool> vis, int node, vector<int> s) {
	vis[node] = true;
	s.push_back(node + 1);
	if (conn[arr - 1].count(node + 1)) {
		if (s.size() < sol.size()) sol = s;
		return;
	}
	for (int to : edges[node]) {
		if (vis[to - 1]) continue;
		solve(vis, to - 1, s);
	}
	return;
}

int main() {
	cin >> n >> m >> beg >> arr;
	conn.resize(m);
	edges.resize(n);
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		for (int j = 0; j < a; j++) {
			int x;
			cin >> x;
			for (int y : conn[x - 1]) {
				edges[i].insert(y);
				edges[y - 1].insert(i + 1);
			}
			conn[x - 1].insert(i + 1);
		}
	}
	for (int i : conn[beg - 1]) {
		solve(vector<bool>(n, false), i - 1, vector<int>(0));
	}
	cout << sol.size() << "\n";
	for (int i : sol) cout << i << " ";
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base18/40
1Elfogadva0/01ms316 KiB
2Időlimit túllépés0/0587ms2612 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms504 KiB
5Elfogadva2/22ms568 KiB
6Hibás válasz0/21ms316 KiB
7Elfogadva2/23ms668 KiB
8Elfogadva2/23ms820 KiB
9Elfogadva2/26ms1588 KiB
10Elfogadva2/24ms1332 KiB
11Elfogadva2/23ms820 KiB
12Időlimit túllépés0/2600ms2428 KiB
13Időlimit túllépés0/2600ms2612 KiB
14Időlimit túllépés0/2600ms2404 KiB
15Időlimit túllépés0/2578ms12400 KiB
16Időlimit túllépés0/2583ms11568 KiB
17Időlimit túllépés0/2586ms11572 KiB
18Időlimit túllépés0/2601ms12596 KiB
19Elfogadva2/26ms2036 KiB
20Időlimit túllépés0/2587ms2356 KiB
21Időlimit túllépés0/2600ms1332 KiB
22Időlimit túllépés0/2600ms2356 KiB