234242026-01-22 18:44:37PappMatyasA lehető legkevesebb metróval utazás (40 pont)cpp17Runtime error 4/40591ms32000 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 vector<int> Finder(int index, int come)
{
	vector<int> lsol;
	int lmin = INTMAX;
	int ideal = -1;
	for (int rIndex : p[index])
	{
		if (rIndex == come) 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 (val == index) continue;
			csol = Finder(val, rIndex);
			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);
		}
	}

	sol = Finder(s, -1);

	if (sol.size() == 0)
	{
		cout << -1;
	}
	else
	{
		cout << sol.size() << endl;
		for (int x : sol)
		{
			cout << x << " ";
		}
	}
}
SubtaskSumTestVerdictTimeMemory
base4/40
1Accepted0/01ms316 KiB
2Runtime error0/0232ms32000 KiB
3Accepted2/21ms316 KiB
4Runtime error0/243ms32000 KiB
5Accepted2/21ms316 KiB
6Runtime error0/246ms32000 KiB
7Runtime error0/250ms32000 KiB
8Time limit exceeded0/2591ms22064 KiB
9Runtime error0/261ms32000 KiB
10Time limit exceeded0/2528ms32000 KiB
11Runtime error0/2193ms32000 KiB
12Runtime error0/2344ms32000 KiB
13Runtime error0/2342ms32000 KiB
14Runtime error0/2301ms32000 KiB
15Runtime error0/2340ms32000 KiB
16Runtime error0/2363ms32000 KiB
17Runtime error0/2349ms32000 KiB
18Runtime error0/2347ms32000 KiB
19Runtime error0/243ms32000 KiB
20Runtime error0/241ms32000 KiB
21Runtime error0/239ms32000 KiB
22Runtime error0/2189ms32000 KiB