8886 2024. 02. 02 20:56:20 bovizdb A lehető legkevesebb metróval utazás (40 pont) cpp17 Hibás válasz 28/40 569ms 8996 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, ind, erk;

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

int main()
{
	cin >> n >> m >> ind >> erk;
	v.resize(n, vector<bool>(n));
	vm.resize(m);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		for (int j = 0; j < a; j++)
		{
			int in;
			cin >> in;
			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;
		while(!q.empty() && x == -1)
		{
			int p = q.front();
			for (int i = 0; i < n; i++)
			{
				if (v[p][i] == 1)
				{
					for (int b : vm[erk-1])
					{
						if (i == b)
						{
							h[i] = p;
							x = b;
							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 && l > 1 && l < out.size())
		{
			out.resize(0);
			int i = x;
			while(i != a)
			{
				out.push_back(i);
				i = h[i];
			}
			out.push_back(i);
			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 Összpont Teszt Verdikt Idő Memória
base 28/40
1 Elfogadva 0/0 3ms 1808 KiB
2 Elfogadva 0/0 8ms 2976 KiB
3 Hibás válasz 0/2 3ms 2312 KiB
4 Elfogadva 2/2 3ms 2420 KiB
5 Hibás válasz 0/2 3ms 2804 KiB
6 Elfogadva 2/2 3ms 2836 KiB
7 Elfogadva 2/2 4ms 3304 KiB
8 Elfogadva 2/2 4ms 3716 KiB
9 Elfogadva 2/2 4ms 3936 KiB
10 Elfogadva 2/2 4ms 4124 KiB
11 Elfogadva 2/2 4ms 3588 KiB
12 Elfogadva 2/2 8ms 4312 KiB
13 Elfogadva 2/2 8ms 4364 KiB
14 Elfogadva 2/2 8ms 4312 KiB
15 Időlimit túllépés 0/2 544ms 8760 KiB
16 Időlimit túllépés 0/2 565ms 8996 KiB
17 Időlimit túllépés 0/2 565ms 8972 KiB
18 Időlimit túllépés 0/2 569ms 8976 KiB
19 Elfogadva 2/2 6ms 4392 KiB
20 Elfogadva 2/2 7ms 4500 KiB
21 Elfogadva 2/2 4ms 4036 KiB
22 Elfogadva 2/2 7ms 4524 KiB