121232024-12-02 22:41:52RRoliA lehető legkevesebb metróval utazás (40 pont)cpp17Időlimit túllépés 32/40600ms7596 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, ind, erk;
vector<vector<int>> allomas;
vector<set<int>> szom;
set<int> kezd, veg;

int main() {
	cin >> n >> m >> ind >> erk;
    szom.resize(n+1);
    allomas.resize(m+1, vector<int>(0));
    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        for(int j = 1; j <= a; j++) {
            int b;
            cin >> b;
            allomas[b].push_back(i);
        }
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j < allomas[i].size(); j++) {
            for(int k = j+1; k < allomas[i].size(); k++) {
                szom[allomas[i][j]].insert(allomas[i][k]);
                szom[allomas[i][k]].insert(allomas[i][j]);
            }
        }
    }
    for(auto j : allomas[ind]) kezd.insert(j);
    for(auto j : allomas[erk]) veg.insert(j);

    int vsor[201], L[201], e = 0, u = -1, elso = -1;
    for(int i = 1; i <= n; i++) L[i] = -2;
    for(auto j : kezd) {
        u++;
        vsor[u] = j;
        L[j] = -1;
    }

    while(e <= u) {
        for(auto j : szom[vsor[e]]) {
            if(L[j] == -2) {
                u++;
                vsor[u] = j;
                L[j] = e;
            }
        }
        e++;
    }

    for(int i = 0; i <= u; i++) {
        if(veg.count(vsor[i]) == 1) {
            elso = i;
            break;
        }
    }

    if(elso == -1) cout << -1;
    else {
        vector<int> sorrend = {vsor[elso]};
        while(L[sorrend[sorrend.size()-1]] != -1) sorrend.push_back(vsor[L[sorrend[sorrend.size()-1]]]);
        cout << sorrend.size() << '\n';
        for(int i = sorrend.size()-1; i >= 0; i--) cout << sorrend[i] << ' ';
    }

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/40
1Elfogadva0/01ms320 KiB
2Elfogadva0/07ms1084 KiB
3Elfogadva2/21ms508 KiB
4Elfogadva2/21ms512 KiB
5Elfogadva2/21ms320 KiB
6Elfogadva2/21ms372 KiB
7Elfogadva2/22ms400 KiB
8Elfogadva2/22ms568 KiB
9Elfogadva2/24ms700 KiB
10Elfogadva2/24ms588 KiB
11Elfogadva2/22ms512 KiB
12Elfogadva2/27ms824 KiB
13Elfogadva2/27ms856 KiB
14Elfogadva2/27ms824 KiB
15Időlimit túllépés0/2600ms7480 KiB
16Időlimit túllépés0/2600ms7480 KiB
17Időlimit túllépés0/2600ms7596 KiB
18Időlimit túllépés0/2600ms7480 KiB
19Elfogadva2/24ms824 KiB
20Elfogadva2/26ms824 KiB
21Elfogadva2/23ms568 KiB
22Elfogadva2/27ms1084 KiB