116432024-11-02 14:31:06MagyarKendeSZLGA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 34/40500ms6492 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);
    int ind_line = 0, erk_line = 0;

    for (int i = 1, K, stop; i <= N; i++) {
        cin >> K;
        vector<int> line(K);

        for (int j = 0; j < K; j++) {
            cin >> line[j];
            stopS[line[j]].push_back(i);
            if (line[j] == Ind) ind_line = i;
            if (line[j] == Erk) erk_line = i;
        }

        if (ind_line == i && erk_line == i) {
            cout << "1\n" << i << "\n";
            exit(0);
        }
    }

    if (!ind_line || !erk_line) {
        cout << "-1\n";
        exit(0);
    }

    vector m(N + 1, vector<bool>(N + 1));

    for (int stop = 1; stop <= M; stop++) {
        for (int i = 0; i < stopS[stop].size(); i++) {
            for (int j = 0; j < i; j++) {
                m[stopS[stop][i]][stopS[stop][j]] = 1;
                m[stopS[stop][j]][stopS[stop][i]] = 1;
            }
        }
    }

    vector<int> distS(N + 1, -1), prv(N + 1);
    queue<int> q({ind_line});

    distS[ind_line] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == erk_line) break;
        for (int v = 1; v <= N; v++) {
            if (m[u][v] && distS[v] == -1) {
                prv[v] = u;
                distS[v] = distS[u] + 1;
                q.push(v);
            }
        }
    }

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

    deque<int> path;
    while (1) {
        path.push_front(erk_line);
        if (erk_line == ind_line) break;
        erk_line = prv[erk_line];
    }

    cout << path.size() << "\n";
    for (int x : path) cout << x << " ";
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base34/40
1Elfogadva0/01ms320 KiB
2Elfogadva0/04ms824 KiB
3Elfogadva2/21ms320 KiB
4Elfogadva2/21ms512 KiB
5Elfogadva2/21ms320 KiB
6Elfogadva2/21ms320 KiB
7Elfogadva2/21ms320 KiB
8Elfogadva2/22ms524 KiB
9Elfogadva2/23ms748 KiB
10Hibás válasz0/22ms568 KiB
11Elfogadva2/21ms320 KiB
12Elfogadva2/24ms824 KiB
13Elfogadva2/24ms824 KiB
14Elfogadva2/24ms1064 KiB
15Elfogadva2/2499ms6388 KiB
16Elfogadva2/2495ms6284 KiB
17Időlimit túllépés0/2500ms6256 KiB
18Elfogadva2/2495ms6492 KiB
19Elfogadva2/23ms656 KiB
20Elfogadva2/23ms712 KiB
21Elfogadva2/22ms568 KiB
22Hibás válasz0/23ms824 KiB