90582024-02-13 14:14:14RRoliA lehető legkevesebb metróval utazás (40 pont)cpp14Wrong answer 18/40301ms36220 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;
}
SubtaskSumTestVerdictTimeMemory
base18/40
1Accepted0/03ms1900 KiB
2Wrong answer0/03ms2860 KiB
3Accepted2/23ms2344 KiB
4Accepted2/23ms2516 KiB
5Accepted2/23ms4144 KiB
6Wrong answer0/23ms2724 KiB
7Accepted2/24ms6520 KiB
8Accepted2/24ms7672 KiB
9Accepted2/28ms12612 KiB
10Wrong answer0/27ms10928 KiB
11Accepted2/24ms6268 KiB
12Wrong answer0/24ms7528 KiB
13Wrong answer0/24ms8156 KiB
14Wrong answer0/23ms4324 KiB
15Wrong answer0/2301ms20524 KiB
16Wrong answer0/2296ms25164 KiB
17Wrong answer0/2294ms29908 KiB
18Wrong answer0/2296ms34992 KiB
19Accepted2/28ms32376 KiB
20Wrong answer0/29ms36220 KiB
21Accepted2/26ms28384 KiB
22Wrong answer0/23ms22276 KiB