116442024-11-02 14:46:57MagyarKendeSZLGA lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 40/40119ms11408 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);

    int N, M, Ind, Erk;
    cin >> N >> M >> Ind >> Erk;

    vector<vector<int>> stopS(M + 1), lineS(N + 1);
    for (int i = 1; i <= N; i++) {
        int A;
        cin >> A;
        while (A--) {
            int stop;
            cin >> stop;
            lineS[i].push_back(stop);
            stopS[stop].push_back(i);
        }
    }

    vector<int> prv_stop(M + 1), prv_line(M + 1),
        distS(M + 1, -1), vis(N + 1);
    queue<int> q({Ind});

    distS[Ind] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : stopS[u]) {
            if (vis[v]) continue;
            vis[v] = 1;
            for (int l : lineS[v]) {
                if (distS[l] != -1) continue;
                distS[l] = distS[u] + 1;
                prv_stop[l] = u;
                prv_line[l] = v;
                q.push(l);
            }
        }
    }

    if (distS[Erk] == -1) {
        cout << "-1\n";
        exit(0);
    }

    cout << distS[Erk] << "\n";

    deque<int> path;
    while (Erk != Ind) {
        path.push_front(prv_line[Erk]);
        Erk = prv_stop[Erk];
    }

    for (int x : path) cout << x << " ";
    cout << "\n";
}

SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/01ms320 KiB
2Accepted0/04ms1080 KiB
3Accepted2/21ms508 KiB
4Accepted2/21ms500 KiB
5Accepted2/21ms320 KiB
6Accepted2/21ms320 KiB
7Accepted2/21ms568 KiB
8Accepted2/22ms568 KiB
9Accepted2/23ms824 KiB
10Accepted2/22ms644 KiB
11Accepted2/21ms568 KiB
12Accepted2/24ms1080 KiB
13Accepted2/24ms1188 KiB
14Accepted2/24ms1148 KiB
15Accepted2/2114ms11136 KiB
16Accepted2/2115ms11320 KiB
17Accepted2/2119ms11408 KiB
18Accepted2/2119ms11292 KiB
19Accepted2/23ms840 KiB
20Accepted2/23ms1032 KiB
21Accepted2/22ms568 KiB
22Accepted2/23ms1080 KiB