234272026-01-22 18:59:21PappMatyasA lehető legkevesebb metróval utazás (40 pont)cpp17Időlimit túllépés 5/40601ms11320 KiB
#include <iostream>
#include <vector>

using namespace std;

vector<int> sol;
vector<vector<int>> rows;
vector<vector<int>> p;

int n, m, s, e;

int INTMAX = 0x7FFFFFFF;

static bool inVector(vector<int>& v, int a)
{
	for (int x : v)
	{
		if (x == a) return true;
	}
	return false;
}

static vector<int> Finder(int index, vector<int>& come)
{
	vector<int> lsol;
	int lmin = INTMAX;
	int ideal = -1;
	vector<int> ccopy = come;
	vector<int> been;
	for (int rIndex : p[index])
	{
		if (inVector(been, rIndex)) continue;
		if (inVector(come, rIndex)) continue;

		been.push_back(rIndex);

		int size = rows[rIndex].size();
		for (int i = 0; i < size; i++)
		{
			int val = rows[rIndex][i];
			if (val == e)
			{
				return vector<int> { rIndex + 1 };
			}
		}
		vector<int> csol;

		for (int i = 0; i < size; i++)
		{
			int val = rows[rIndex][i];
			if (val == index) continue;

			ccopy.push_back(rIndex);

			csol = Finder(val, ccopy);

			ccopy.pop_back();

			int size = csol.size();
			if (size < lmin)
			{
				ideal = rIndex;
				lsol = csol;
			}
		}
	}
	lsol.insert(lsol.begin(), ideal + 1);
	return lsol;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> s >> e;

	s--;
	e--;

	for (int i = 0; i < m; i++)
	{
		p.push_back(vector<int>{});
	}

	for (int i = 0; i < n; i++)
	{
		rows.push_back(vector<int>{});
		int x;
		cin >> x;
		for (int j = 0; j < x; j++)
		{
			int y;
			cin >> y;
			y--;
			rows[i].push_back(y);
			p[y].push_back(i);
		}
	}
	vector<int> a{};

	sol = Finder(s, a);

	if (sol.size() == 0)
	{
		cout << -1;
	}
	else
	{
		cout << sol.size() << endl;
		for (int x : sol)
		{
			cout << x << " ";
		}
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base5/40
1Elfogadva0/01ms316 KiB
2Időlimit túllépés0/0574ms1072 KiB
3Elfogadva2/21ms316 KiB
4Részben helyes1/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Időlimit túllépés0/2600ms564 KiB
8Időlimit túllépés0/2583ms568 KiB
9Időlimit túllépés0/2583ms756 KiB
10Időlimit túllépés0/2578ms564 KiB
11Időlimit túllépés0/2592ms512 KiB
12Időlimit túllépés0/2598ms972 KiB
13Időlimit túllépés0/2600ms1072 KiB
14Időlimit túllépés0/2588ms1072 KiB
15Időlimit túllépés0/2591ms11320 KiB
16Időlimit túllépés0/2601ms11252 KiB
17Időlimit túllépés0/2601ms11252 KiB
18Időlimit túllépés0/2573ms11288 KiB
19Időlimit túllépés0/2600ms756 KiB
20Időlimit túllépés0/2598ms812 KiB
21Időlimit túllépés0/2600ms564 KiB
22Időlimit túllépés0/2578ms1072 KiB