148222025-02-03 14:29:58KateTaylorA lehető legkevesebb metróval utazás (40 pont)cpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
base18/40
1Accepted0/01ms316 KiB
2Time limit exceeded0/0587ms2612 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms504 KiB
5Accepted2/22ms568 KiB
6Wrong answer0/21ms316 KiB
7Accepted2/23ms668 KiB
8Accepted2/23ms820 KiB
9Accepted2/26ms1588 KiB
10Accepted2/24ms1332 KiB
11Accepted2/23ms820 KiB
12Time limit exceeded0/2600ms2428 KiB
13Time limit exceeded0/2600ms2612 KiB
14Time limit exceeded0/2600ms2404 KiB
15Time limit exceeded0/2578ms12400 KiB
16Time limit exceeded0/2583ms11568 KiB
17Time limit exceeded0/2586ms11572 KiB
18Time limit exceeded0/2601ms12596 KiB
19Accepted2/26ms2036 KiB
20Time limit exceeded0/2587ms2356 KiB
21Time limit exceeded0/2600ms1332 KiB
22Time limit exceeded0/2600ms2356 KiB