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