6955 2023. 12. 21 10:36:29 tamasmark A lehető legkevesebb metróval utazás (40 pont) cpp17 Futási hiba 10/40 17ms 4984 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
Részfeladat Összpont Teszt Verdikt Idő Memória
base 10/40
1 Elfogadva 0/0 3ms 1812 KiB
2 Futási hiba 0/0 4ms 2892 KiB
3 Hibás válasz 0/2 3ms 2316 KiB
4 Elfogadva 2/2 3ms 2484 KiB
5 Elfogadva 2/2 3ms 2636 KiB
6 Hibás válasz 0/2 3ms 2704 KiB
7 Elfogadva 2/2 4ms 3196 KiB
8 Elfogadva 2/2 4ms 3340 KiB
9 Elfogadva 2/2 6ms 4040 KiB
10 Hibás válasz 0/2 4ms 3912 KiB
11 Futási hiba 0/2 3ms 3564 KiB
12 Futási hiba 0/2 3ms 4000 KiB
13 Futási hiba 0/2 6ms 4304 KiB
14 Futási hiba 0/2 4ms 4056 KiB
15 Futási hiba 0/2 17ms 4840 KiB
16 Futási hiba 0/2 12ms 4680 KiB
17 Futási hiba 0/2 14ms 4728 KiB
18 Futási hiba 0/2 14ms 4984 KiB
19 Futási hiba 0/2 4ms 4324 KiB
20 Futási hiba 0/2 4ms 4408 KiB
21 Futási hiba 0/2 3ms 4104 KiB
22 Futási hiba 0/2 3ms 4376 KiB