116402024-11-02 12:52:55MagyarKendeSZLGA lehető legkevesebb metróval utazás (40 pont)cpp17Runtime error 26/40504ms32000 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);
        }
    }

    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
base26/40
1Accepted0/01ms320 KiB
2Accepted0/04ms824 KiB
3Accepted2/21ms320 KiB
4Accepted2/21ms320 KiB
5Accepted2/21ms320 KiB
6Runtime error0/268ms32000 KiB
7Accepted2/22ms320 KiB
8Accepted2/22ms528 KiB
9Accepted2/22ms760 KiB
10Wrong answer0/22ms588 KiB
11Accepted2/21ms320 KiB
12Accepted2/24ms828 KiB
13Accepted2/24ms824 KiB
14Accepted2/23ms824 KiB
15Time limit exceeded0/2500ms6432 KiB
16Time limit exceeded0/2504ms6304 KiB
17Time limit exceeded0/2500ms6380 KiB
18Time limit exceeded0/2504ms6456 KiB
19Accepted2/23ms656 KiB
20Accepted2/23ms1004 KiB
21Accepted2/22ms568 KiB
22Wrong answer0/23ms824 KiB