247982026-02-15 13:50:21miszorimarciA lehető legkevesebb metróval utazás (40 pont)cpp17Időlimit túllépés 36/40513ms11276 KiB
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;cin >> n >> m >> s >> t;
    vector<vector<int>> station(m + 1);
    vector<vector<int>> line(n + 1);

    for (int i = 1; i <= n; ++i) {
        int cnt;cin >> cnt;
        for (int j = 0; j < cnt; ++j) {
            int x; cin >> x;
            line[i].push_back(x);
            station[x].push_back(i);
        }
    }

    queue<int> q;
    vector<int> d(n + 1, -1);  
    vector<int> p(n + 1, 0); 
    vector<bool> target(n + 1, false);

    for (int i : station[s]) {
        d[i] = 1;
        q.push(i);
    }

    for (int i : station[t]) {
        target[i] = true;
    }

    int final = -1;

    for (int i : station[s]) {
        if (target[i]) {
            final = i;
            break;
        }
    }

    if (final == -1) {
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (target[u]) {
                final = u;
                break;
            }
            for (int s : line[u]) {
                for (int v : station[s]) {
                    if (d[v] == -1) {
                        d[v] = d[u] + 1;
                        p[v] = u;
                        q.push(v);
                    }
                }
            }
        }
    }

    if (final == -1) {
        cout << -1 << "\n";
    } else {
        cout << d[final] << "\n";
        vector<int> path;
        int curr = final;
        while (curr != 0) {
            path.push_back(curr);
            curr = p[curr];
        }
        reverse(path.begin(), path.end());

        for (int i = 0; i < path.size(); ++i) {
            cout << path[i] << (i == path.size() - 1 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base36/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/04ms820 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/22ms564 KiB
8Elfogadva2/22ms572 KiB
9Elfogadva2/22ms664 KiB
10Elfogadva2/22ms564 KiB
11Elfogadva2/21ms316 KiB
12Elfogadva2/24ms828 KiB
13Elfogadva2/24ms1024 KiB
14Elfogadva2/23ms820 KiB
15Elfogadva2/2421ms11084 KiB
16Időlimit túllépés0/2509ms11276 KiB
17Elfogadva2/2426ms11224 KiB
18Időlimit túllépés0/2513ms11068 KiB
19Elfogadva2/23ms820 KiB
20Elfogadva2/23ms820 KiB
21Elfogadva2/22ms748 KiB
22Elfogadva2/23ms960 KiB