116412024-11-02 12:54:18MagyarKendeSZLGA lehető legkevesebb metróval utazás (40 pont)cpp17Wrong answer 30/40504ms6544 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 || !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, INT_MAX), vis(N + 1),
        prv(N + 1);
    queue<int> q({ind_line});

    vis[ind_line] = 1;
    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] || vis[v]) continue;
            vis[v] = 1;
            prv[v] = u;
            distS[v] = distS[u] + 1;
            q.push(v);
        }
    }

    if (distS[erk_line] == INT_MAX) {
        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";
}
SubtaskSumTestVerdictTimeMemory
base30/40
1Accepted0/01ms320 KiB
2Accepted0/04ms824 KiB
3Accepted2/21ms320 KiB
4Accepted2/21ms500 KiB
5Accepted2/21ms348 KiB
6Accepted2/21ms420 KiB
7Accepted2/21ms320 KiB
8Accepted2/22ms572 KiB
9Accepted2/22ms568 KiB
10Wrong answer0/22ms620 KiB
11Accepted2/21ms360 KiB
12Accepted2/24ms980 KiB
13Accepted2/24ms908 KiB
14Accepted2/24ms1020 KiB
15Accepted2/2497ms6516 KiB
16Time limit exceeded0/2504ms6288 KiB
17Time limit exceeded0/2504ms6376 KiB
18Time limit exceeded0/2503ms6544 KiB
19Accepted2/23ms760 KiB
20Accepted2/23ms932 KiB
21Accepted2/22ms568 KiB
22Wrong answer0/23ms824 KiB