88652024-02-02 16:57:12bovizdbA lehető legkevesebb metróval utazás (40 pont)cpp17Runtime error 1/40578ms28664 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(200);
	for (int a : vm[ind-1])
	{
		vector <int> c(n);
		vector <int> mn = {a};
		queue<int> q;
		q.push(ind-1);
		bool br = 1;
		while(!q.empty() && br)
		{
			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)
						{
							br = 0;
							break;
						}
					}
				}
				if (v[p][i] == 1 && c[v[p][i]] == 0)
				{
					c[v[p][i]] = 1;
					q.push(i);
				}
			}
			if (p == mn.back())
			{
				mn.push_back(q.back());
			}
			q.pop();
		}
		if (mn.size() < out.size()) out = mn;
	}
	cout << out.size() << endl;
	for (int i : out) cout << i+1 << " ";
}
SubtaskSumTestVerdictTimeMemory
base1/40
1Accepted0/03ms1852 KiB
2Runtime error0/07ms3448 KiB
3Partially correct1/23ms2468 KiB
4Wrong answer0/23ms2596 KiB
5Runtime error0/23ms2828 KiB
6Wrong answer0/23ms2820 KiB
7Wrong answer0/24ms3272 KiB
8Runtime error0/24ms3728 KiB
9Runtime error0/26ms3964 KiB
10Wrong answer0/24ms3868 KiB
11Runtime error0/24ms3640 KiB
12Runtime error0/28ms4908 KiB
13Runtime error0/28ms5188 KiB
14Runtime error0/28ms5520 KiB
15Time limit exceeded0/2574ms14304 KiB
16Time limit exceeded0/2577ms19256 KiB
17Time limit exceeded0/2578ms24004 KiB
18Time limit exceeded0/2555ms28664 KiB
19Runtime error0/26ms24408 KiB
20Runtime error0/27ms25064 KiB
21Wrong answer0/24ms24496 KiB
22Runtime error0/28ms25560 KiB