89092024-02-04 12:32:28bovizdbA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 28/40600ms9188 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, ind, erk;

vector<vector<bool>> v;
vector<vector<int>> vm;
vector<vector<int>> memo;

int main()
{
	cin >> n >> m >> ind >> erk;
	v.resize(n, vector<bool>(n));
	vm.resize(m);
	memo.resize(n);
	vector<bool> verk(n);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		for (int j = 0; j < a; j++)
		{
			int in;
			cin >> in;
			if (in == erk) verk[i] = 1;
			vm[in-1].push_back(i);
		}
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < vm[i].size(); j++)
		{
			for (int k = j+1; k < vm[i].size(); k++)
			{
				v[vm[i][j]][vm[i][k]] = 1;
				v[vm[i][k]][vm[i][j]] = 1;
			}
		}
	}
	vector<int> out(210);
	for (int a : vm[ind-1])
	{
		vector <int> c(n);
		vector<int> h(n);
		queue<int> q;
		int x = -1;
		q.push(a);
		int l = 1, u = a;
		bool bm = 0;
		while(!q.empty() && x == -1)
		{
			int p = q.front();
			for (int i = 0; i < n; i++)
			{
				if (v[p][i] == 1)
				{
					if (memo[v[p][i]].size() > 0)
					{
						if (memo[v[p][i]].size() + l-1 < out.size())
						{
							bm = 1;
							out = memo[i];
							h[i] = p;
							x = i;
							break;
						}
						else
						{
							x = -2;
							break;
						}
					}
					if (verk[i] == 1)
					{
						h[i] = p;
						x = i;
						break;
					}
				}
				if (v[p][i] == 1 && c[i] == 0)
				{
					c[i] = 1;
					q.push(i);
					h[i] = p;
				}
			}
			if (p == u)
			{
				l++;
				u = q.back();
			}
			q.pop();
		}
		if (x >= 0)
		{
			if (bm)
			{
				int i = h[x];
				while(i != a)
				{
					out.push_back(i);
					memo[i] = out;
					i = h[i];
				}
				out.push_back(i);
				memo[a] = out;
				reverse(out.begin(), out.end());
			}
			else if (l < out.size())
			{
				out.resize(0);
				int i = x;
				while(i != a)
				{
					out.push_back(i);
					memo[i] = out;
					i = h[i];
				}
				out.push_back(i);
				memo[a] = out;
				reverse(out.begin(), out.end());
			}
		}
	}
	if (out.size() == 210) cout << -1;
	else
	{		
		cout << out.size() << endl;
		for (int i : out) cout << i+1 << " ";
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/40
1Elfogadva0/03ms1688 KiB
2Elfogadva0/07ms2908 KiB
3Hibás válasz0/23ms2136 KiB
4Elfogadva2/23ms2348 KiB
5Hibás válasz0/23ms2740 KiB
6Elfogadva2/22ms2564 KiB
7Elfogadva2/24ms2952 KiB
8Elfogadva2/24ms3360 KiB
9Elfogadva2/26ms3568 KiB
10Elfogadva2/24ms3648 KiB
11Elfogadva2/24ms3572 KiB
12Elfogadva2/28ms4276 KiB
13Elfogadva2/28ms4560 KiB
14Elfogadva2/28ms4600 KiB
15Időlimit túllépés0/2600ms8976 KiB
16Időlimit túllépés0/2570ms9188 KiB
17Időlimit túllépés0/2566ms9012 KiB
18Időlimit túllépés0/2509ms9092 KiB
19Elfogadva2/26ms4516 KiB
20Elfogadva2/27ms4584 KiB
21Elfogadva2/24ms4260 KiB
22Elfogadva2/27ms4744 KiB