69552023-12-21 10:36:29tamasmarkA lehető legkevesebb metróval utazás (40 pont)cpp17Runtime error 10/4017ms4984 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;
    x[v.front()].lat = true;
    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
SubtaskSumTestVerdictTimeMemory
base10/40
1Accepted0/03ms1812 KiB
2Runtime error0/04ms2892 KiB
3Wrong answer0/23ms2316 KiB
4Accepted2/23ms2484 KiB
5Accepted2/23ms2636 KiB
6Wrong answer0/23ms2704 KiB
7Accepted2/24ms3196 KiB
8Accepted2/24ms3340 KiB
9Accepted2/26ms4040 KiB
10Wrong answer0/24ms3912 KiB
11Runtime error0/23ms3564 KiB
12Runtime error0/23ms4000 KiB
13Runtime error0/26ms4304 KiB
14Runtime error0/24ms4056 KiB
15Runtime error0/217ms4840 KiB
16Runtime error0/212ms4680 KiB
17Runtime error0/214ms4728 KiB
18Runtime error0/214ms4984 KiB
19Runtime error0/24ms4324 KiB
20Runtime error0/24ms4408 KiB
21Runtime error0/23ms4104 KiB
22Runtime error0/23ms4376 KiB