9058 | 2024. 02. 13 14:14:14 | RRoli | A lehető legkevesebb metróval utazás (40 pont) | cpp14 | Hibás válasz 18/40 | 301ms | 36220 KiB |
#include <iostream>
using namespace std;
int n, m, ind, veg, a[10000][200], sz[10000], lk = 200, jo[200];
bool ma[200][200], vegso[200];
void bejar(int k) {
int vsor[200], L[200], elso = 1, utolso = 1;
vsor[1] = k;
for(int i = 1; i <= m; i++) L[i] = -1;
L[k] = 0;
while(elso <= utolso && !vegso[vsor[utolso]]) {
int t = vsor[elso];
for(int i = 1; i <= m; i++) {
if(ma[i][t] && L[i] == -1) {
utolso++;
vsor[utolso] = i;
L[i] = t;
if(vegso[vsor[utolso]]) break;
}
}
elso++;
}
int t = vsor[utolso], sz = 1, ut[200];
ut[1] = t;
while(L[t] != 0) {
t = L[t];
sz++;
ut[sz] = t;
}
if(sz < lk) {
lk = sz;
for(int i = 1; i <= sz; i++)
jo[i] = ut[i];
}
}
int main()
{
cin >> m >> n >> ind >> veg;
for(int i = 1; i <= m; i++) {
int x;
cin >> x;
for(int j = 1; j <= x; j++) {
int y;
cin >> y;
sz[y]++;
a[y][sz[y]] = i;
if(y == veg) vegso[i] = true;
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= sz[i]-1; i++)
for(int k = j+1; k <= sz[i]; k++) {
ma[a[i][k]][a[i][j]] = true; ma[a[i][j]][a[i][k]] = true;
}
for(int i = 1; i <= sz[ind]; i++)
bejar(a[ind][i]);
cout << lk << endl;
for(int i = lk; i >= 1; i--)
cout << jo[i] << ' ';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 18/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1900 KiB | |||
2 | Hibás válasz | 0/0 | 3ms | 2860 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2344 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2516 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 4144 KiB | |||
6 | Hibás válasz | 0/2 | 3ms | 2724 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 6520 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 7672 KiB | |||
9 | Elfogadva | 2/2 | 8ms | 12612 KiB | |||
10 | Hibás válasz | 0/2 | 7ms | 10928 KiB | |||
11 | Elfogadva | 2/2 | 4ms | 6268 KiB | |||
12 | Hibás válasz | 0/2 | 4ms | 7528 KiB | |||
13 | Hibás válasz | 0/2 | 4ms | 8156 KiB | |||
14 | Hibás válasz | 0/2 | 3ms | 4324 KiB | |||
15 | Hibás válasz | 0/2 | 301ms | 20524 KiB | |||
16 | Hibás válasz | 0/2 | 296ms | 25164 KiB | |||
17 | Hibás válasz | 0/2 | 294ms | 29908 KiB | |||
18 | Hibás válasz | 0/2 | 296ms | 34992 KiB | |||
19 | Elfogadva | 2/2 | 8ms | 32376 KiB | |||
20 | Hibás válasz | 0/2 | 9ms | 36220 KiB | |||
21 | Elfogadva | 2/2 | 6ms | 28384 KiB | |||
22 | Hibás válasz | 0/2 | 3ms | 22276 KiB |