9477 2024. 02. 22 10:35:03 csaron71 A lehető legkevesebb metróval utazás (40 pont) cpp17 Hibás válasz 24/40 61ms 63792 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, kezd, veg;
    cin >> n >> m >> kezd >> veg;
    kezd--;
    veg--;
    vector<vector<pair<int, int> > > graph(m, vector<pair<int, int> >());
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        vector<int> epp;
        for (int i=0; i<x; i++) {
            int y;
            cin >> y;
            y--;
            epp.push_back(y);
        }
        for (int q=0; q<x; q++) {
            for (int j=q+1; j<x; j++) {
                graph[epp[q]].push_back({epp[j], i+1});
                graph[epp[j]].push_back({epp[q], i+1});
            }
        }
    }

    queue<pair<pair<int, int>, pair<int, int> > > sor; // melyik, milyen messze, honnan, melyik metro
    vector<bool> volt(m, false);
    vector<int> tav(m, -1);
    sor.push({{kezd, 0}, {0, 0}});
    tav[kezd]=0;
    vector<int> honnan(m);
    vector<int> metro(m);

    while (sor.size()>0) {
        int elso=sor.front().first.first;
        int hany=sor.front().first.second;
        int mibol=sor.front().second.first;
        int melyik=sor.front().second.second;
        sor.pop();
        if (volt[elso]==true) continue;
        tav[elso]=hany;
        volt[elso]=true;
        honnan[elso]=mibol;
        metro[elso]=melyik;

        for (pair<int, int> sz : graph[elso]) {
            if (volt[sz.first]!=true) {
                sor.push({{sz.first, hany+1}, {elso, sz.second}});
            }
        }
    }

    cout << tav[veg] << "\n";

    vector<int> vege;
    int most=veg;
    while (most!=kezd) {
        //cout << most << " ";
        vege.push_back(metro[most]);
        most=honnan[most];
    }
    //cout << "\n";
    reverse(vege.begin(), vege.end());
    for (int sz : vege) {
        cout << sz << " ";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 24/40
1 Elfogadva 0/0 3ms 1820 KiB
2 Elfogadva 0/0 41ms 24996 KiB
3 Elfogadva 2/2 3ms 2260 KiB
4 Elfogadva 2/2 3ms 2456 KiB
5 Elfogadva 2/2 8ms 8472 KiB
6 Hibás válasz 0/2 3ms 2760 KiB
7 Elfogadva 2/2 41ms 34212 KiB
8 Futási hiba 0/2 59ms 63792 KiB
9 Futási hiba 0/2 59ms 63552 KiB
10 Futási hiba 0/2 61ms 63524 KiB
11 Elfogadva 2/2 12ms 11532 KiB
12 Elfogadva 2/2 46ms 32972 KiB
13 Elfogadva 2/2 46ms 32700 KiB
14 Elfogadva 2/2 41ms 29000 KiB
15 Futási hiba 0/2 61ms 63196 KiB
16 Futási hiba 0/2 59ms 63176 KiB
17 Futási hiba 0/2 59ms 63164 KiB
18 Futási hiba 0/2 59ms 63140 KiB
19 Elfogadva 2/2 19ms 13668 KiB
20 Elfogadva 2/2 32ms 22904 KiB
21 Elfogadva 2/2 9ms 7656 KiB
22 Elfogadva 2/2 39ms 26560 KiB