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 |