234302026-01-22 19:07:27PappMatyasA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 7/40601ms11352 KiB
#include <iostream>
#include <vector>

using namespace std;

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

vector<vector<int>> dictionary;

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 (dictionary[rIndex].size() != 0)
		{
			int size = dictionary[rIndex].size();
			if (size < lmin)
			{
				ideal = rIndex;
				lsol = dictionary[rIndex];
			}
			continue;
		}
		if (inVector(come, rIndex)) continue;

		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 (inVector(been, val)) continue;
			if (val == index) continue;

			been.push_back(val);
			ccopy.push_back(rIndex);

			csol = Finder(val, ccopy);

			ccopy.pop_back();

			int size = csol.size();
			if (size < lmin)
			{
				ideal = rIndex;
				lsol = csol;
			}
		}
		dictionary[rIndex] = 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++)
	{
		dictionary.push_back(vector<int>{});
		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
base7/40
1Elfogadva0/01ms316 KiB
2Hibás válasz0/07ms1072 KiB
3Elfogadva2/21ms316 KiB
4Részben helyes1/21ms508 KiB
5Elfogadva2/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Hibás válasz0/22ms576 KiB
8Részben helyes1/22ms748 KiB
9Részben helyes1/24ms756 KiB
10Hibás válasz0/24ms696 KiB
11Hibás válasz0/22ms564 KiB
12Hibás válasz0/28ms1212 KiB
13Hibás válasz0/27ms1068 KiB
14Hibás válasz0/27ms1072 KiB
15Időlimit túllépés0/2601ms11308 KiB
16Időlimit túllépés0/2583ms11252 KiB
17Időlimit túllépés0/2600ms11228 KiB
18Időlimit túllépés0/2601ms11352 KiB
19Hibás válasz0/24ms756 KiB
20Hibás válasz0/26ms1068 KiB
21Hibás válasz0/23ms820 KiB
22Hibás válasz0/24ms1136 KiB