148142025-02-03 11:12:49KateTaylorA lehető legkevesebb metróval utazás (40 pont)cpp17Időlimit túllépés 4/40601ms32000 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) {
		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, first, prev;
		cin >> k >> first;
		prev = first;
		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;
			if (j == k - 1) {
				edges[x - 1].push_back({ i + 1, first - 1 });
				edges[first - 1].push_back({ i + 1, x - 1 });
			}
		}
	}
	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
base4/40
1Elfogadva0/01ms508 KiB
2Időlimit túllépés0/0587ms10032 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Hibás válasz0/21ms316 KiB
7Időlimit túllépés0/2600ms796 KiB
8Időlimit túllépés0/2600ms1844 KiB
9Időlimit túllépés0/2600ms5796 KiB
10Időlimit túllépés0/2578ms2356 KiB
11Időlimit túllépés0/2600ms692 KiB
12Időlimit túllépés0/2600ms1844 KiB
13Időlimit túllépés0/2600ms1688 KiB
14Időlimit túllépés0/2583ms14900 KiB
15Időlimit túllépés0/2601ms32000 KiB
16Időlimit túllépés0/2591ms31804 KiB
17Időlimit túllépés0/2592ms31996 KiB
18Időlimit túllépés0/2587ms32000 KiB
19Időlimit túllépés0/2587ms3380 KiB
20Időlimit túllépés0/2600ms10808 KiB
21Időlimit túllépés0/2600ms4148 KiB
22Időlimit túllépés0/2583ms3124 KiB