94782024-02-22 10:35:57csaron71A lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 24/4059ms64000 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m, kezd, veg;
    cin >> n >> m >> kezd >> veg;
    kezd--;
    veg--;
    vector<vector<pair<long long, long long> > > graph(m, vector<pair<long long, long long> >());
    for (long long i=0; i<n; i++) {
        long long x;
        cin >> x;
        vector<long long> epp;
        for (long long i=0; i<x; i++) {
            long long y;
            cin >> y;
            y--;
            epp.push_back(y);
        }
        for (long long q=0; q<x; q++) {
            for (long long 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<long long, long long>, pair<long long, long long> > > sor; // melyik, milyen messze, honnan, melyik metro
    vector<bool> volt(m, false);
    vector<long long> tav(m, -1);
    sor.push({{kezd, 0}, {0, 0}});
    tav[kezd]=0;
    vector<long long> honnan(m);
    vector<long long> metro(m);

    while (sor.size()>0) {
        long long elso=sor.front().first.first;
        long long hany=sor.front().first.second;
        long long mibol=sor.front().second.first;
        long long 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<long long, long long> sz : graph[elso]) {
            if (volt[sz.first]!=true) {
                sor.push({{sz.first, hany+1}, {elso, sz.second}});
            }
        }
    }

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

    vector<long long> vege;
    long long most=veg;
    while (most!=kezd) {
        //cout << most << " ";
        vege.push_back(metro[most]);
        most=honnan[most];
    }
    //cout << "\n";
    reverse(vege.begin(), vege.end());
    for (long long sz : vege) {
        cout << sz << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base24/40
1Elfogadva0/03ms1816 KiB
2Elfogadva0/048ms46904 KiB
3Elfogadva2/23ms2120 KiB
4Elfogadva2/23ms2332 KiB
5Elfogadva2/29ms13756 KiB
6Hibás válasz0/23ms2764 KiB
7Elfogadva2/252ms64000 KiB
8Futási hiba0/241ms63888 KiB
9Futási hiba0/243ms63652 KiB
10Futási hiba0/245ms63660 KiB
11Elfogadva2/214ms19332 KiB
12Elfogadva2/259ms60424 KiB
13Elfogadva2/259ms60148 KiB
14Elfogadva2/252ms52912 KiB
15Futási hiba0/248ms63520 KiB
16Futási hiba0/246ms63540 KiB
17Futási hiba0/246ms63516 KiB
18Futási hiba0/246ms63504 KiB
19Elfogadva2/225ms23156 KiB
20Elfogadva2/241ms41284 KiB
21Elfogadva2/212ms10772 KiB
22Elfogadva2/248ms47956 KiB