69542023-12-21 10:34:56tamasmarkA lehető legkevesebb metróval utazás (40 pont)cpp17Futási hiba 2/4059ms64500 KiB
// legkevesebbmatro.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>

using namespace std;

struct adat
{
    int lep,lat,honnan;
    bool veg,kezd;
    vector<int>szelek;
    vector<int>allomasok;
};
int n, m, i, j, k, a, b,kezd,veg;
int main()
{
    cin >> m >> n >> kezd >> veg;
    vector<adat>x(m + 1);
    deque<int>v,megold;
    vector<vector<int>>csp(n+1);
    for (i = 1; i <= m; ++i)
    {
        cin >> a;
        for (j = 1; j <= a; ++j)
        {
            cin >> b;
            if (!csp[b].size()) csp[b].push_back(i);
            else
            {
                for (auto& e : csp[b])
                {
                    auto it = find(x[i].szelek.begin(), x[i].szelek.end(), e);
                    if (it == x[i].szelek.end())
                    {
                        x[i].szelek.push_back(e);
                        x[e].szelek.push_back(i);
                        csp[b].push_back(i);
                    }
                }
            }
            x[i].allomasok.push_back(b);
            if (b == veg) x[i].veg = true;
            if (b == kezd) v.push_back(i);
        }
    }
    x[v.front()].lep = 1;
    while (!v.empty())
    {
        auto akt = v.front();
        v.pop_front();
        if (x[akt].veg)
        {
            cout << x[akt].lep << "\n";
            while (akt)
            {
                megold.push_front(akt);
                akt = x[akt].honnan;
            }
            for (auto& e : megold) cout << e << " ";
            break;
        }
        for (auto& e : x[akt].szelek)
        {
            if (!x[e].lat)
            {
                x[e].lep = x[akt].lep + 1;
                x[e].honnan = akt;
                x[e].lat = true;
                v.push_back(e);
            }
        }
    }
    return 0;
}
/*
3 12 1 8
6 1 2 3 4 5 6
6 4 5 6 7 8 9
5 3 10 11 12 7
*/
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/40
1Elfogadva0/03ms1812 KiB
2Futási hiba0/04ms2832 KiB
3Hibás válasz0/23ms2416 KiB
4Futási hiba0/254ms64500 KiB
5Elfogadva2/23ms2620 KiB
6Hibás válasz0/23ms2652 KiB
7Futási hiba0/254ms64132 KiB
8Futási hiba0/254ms63868 KiB
9Futási hiba0/259ms63612 KiB
10Futási hiba0/254ms63568 KiB
11Futási hiba0/24ms3828 KiB
12Futási hiba0/23ms4496 KiB
13Futási hiba0/26ms5296 KiB
14Futási hiba0/24ms5132 KiB
15Futási hiba0/217ms6048 KiB
16Futási hiba0/212ms6168 KiB
17Futási hiba0/214ms6584 KiB
18Futási hiba0/214ms6956 KiB
19Futási hiba0/23ms6332 KiB
20Futási hiba0/24ms6684 KiB
21Futási hiba0/23ms6400 KiB
22Futási hiba0/23ms6828 KiB