9219 2024-02-18 18:47:54 xxx A lehető legkevesebb metróval utazás (40 pont) cpp14 Elfogadva 40/40 485ms 15812 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
int n, m, ind, erk;
cin >> n >> m >> ind >> erk;
vector<vector<int> > megall(m+1);
vector<vector<bool> > el(n+1, vector<bool>(n+1, false));
for(int i = 0; i < n; i++) {
int db;
cin >> db;
for(int j = 0; j < db; j++) {
int x;
cin >> x;
megall[x].push_back(i);
}
}

for(int i = 1; i <= m; i++) {
if (megall[i].size() > 1) {
for(int j = 0; j < megall[i].size(); j++) {
for(int k = j+1; k < megall[i].size(); k++) {
el[megall[i][j]][megall[i][k]] = 1;
el[megall[i][k]][megall[i][j]] = 1;
}
}
}
}
queue<int> q;
vector<int> tav(n+1, -1), parent(n+1, -1);

for(int i : megall[ind]) {
q.push(i);
tav[i] = 1;
}

while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = 0; i < n; i++) {
if (el[u][i]) {
if (tav[i] == -1) {
tav[i] = tav[u]+1;
parent[i] = u;
q.push(i);
}
}
}
}

int ans = INT_MAX, mini = 0;
for(int i : megall[erk]) {
if (tav[i] == -1) {
cout << "-1\n";
return 0;
}
if (ans > tav[i]) {
ans = tav[i];
mini = i;
}
}

cout << ans << '\n';

vector<int> ansv;

while(ans--) {
ansv.push_back(mini);
mini = parent[mini];
}
reverse(ansv.begin(), ansv.end());
for(int x : ansv) {
cout << x+1 << ' ';
}

return 0;
}