148152025-02-03 11:27:45KateTaylorA lehető legkevesebb metróval utazás (40 pont)cpp17Időlimit túllépés 6/40601ms29084 KiB
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int n, m, beg, arr, best = INT_MAX;
vector<vector<pair<int, int>>> edges;
vector<int> sol;

void solve(vector<bool> vis, vector<int> s, int node) {
	vis[node] = true;
	if (node == arr - 1) {
		if (s.size() < best) {
			best = s.size();
			sol = s;
		}
		return;
	}
	for (pair<int, int> p : edges[node]) {
		int x = p.second, r = p.first;
		if (vis[x]) continue;
		bool added = false;
		if (s.empty()) {
			added = true;
			s.push_back(r);
		}
		if (s.back() != r) {
			added = true;
			s.push_back(r);
		}
		solve(vis, s, x);
		if (added) s.pop_back();
	}
	return;
}

int main() {
	cin >> n >> m >> beg >> arr;
	edges.resize(m);
	for (int i = 0; i < n; i++) {
		int k, prev;
		cin >> k >> prev;
		for (int j = 1; j < k; j++) {
			int x;
			cin >> x;
			edges[x - 1].push_back({ i + 1, prev - 1 });
			edges[prev - 1].push_back({ i + 1, x - 1 });
			prev = x;
		}
	}
	solve(vector<bool>(m, false), vector<int>(0), beg - 1);
	cout << sol.size() << "\n";
	for (int x : sol) cout << x << " ";
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base6/40
1Elfogadva0/01ms316 KiB
2Időlimit túllépés0/0583ms6216 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Időlimit túllépés0/2598ms812 KiB
8Időlimit túllépés0/2600ms1932 KiB
9Időlimit túllépés0/2600ms6196 KiB
10Időlimit túllépés0/2586ms1332 KiB
11Időlimit túllépés0/2583ms568 KiB
12Időlimit túllépés0/2601ms9944 KiB
13Időlimit túllépés0/2601ms10036 KiB
14Időlimit túllépés0/2587ms12976 KiB
15Időlimit túllépés0/2601ms29084 KiB
16Időlimit túllépés0/2582ms26932 KiB
17Időlimit túllépés0/2582ms27444 KiB
18Időlimit túllépés0/2578ms28212 KiB
19Időlimit túllépés0/2600ms5972 KiB
20Időlimit túllépés0/2589ms6452 KiB
21Időlimit túllépés0/2589ms1824 KiB
22Időlimit túllépés0/2583ms4148 KiB