148212025-02-03 13:54:52KateTaylorA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 10/40600ms12564 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]) return;
		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
base10/40
1Elfogadva0/01ms316 KiB
2Hibás válasz0/08ms2356 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms508 KiB
5Elfogadva2/22ms564 KiB
6Hibás válasz0/21ms316 KiB
7Hibás válasz0/23ms820 KiB
8Elfogadva2/23ms820 KiB
9Elfogadva2/24ms1588 KiB
10Hibás válasz0/24ms1332 KiB
11Hibás válasz0/23ms820 KiB
12Hibás válasz0/28ms2576 KiB
13Hibás válasz0/29ms2428 KiB
14Hibás válasz0/28ms2356 KiB
15Időlimit túllépés0/2600ms12564 KiB
16Időlimit túllépés0/2584ms12516 KiB
17Időlimit túllépés0/2586ms11572 KiB
18Időlimit túllépés0/2587ms11664 KiB
19Hibás válasz0/26ms1844 KiB
20Hibás válasz0/28ms2112 KiB
21Hibás válasz0/24ms1332 KiB
22Hibás válasz0/28ms2552 KiB