151332025-02-13 11:32:47tamasmarkA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 18/40492ms1404 KiB
// leheto legkevesebb metro.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

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

using namespace std;
struct adat
{
    int lat,lep,veg,honnan,kezd;
    set<int>sz;
};
struct adat2
{
    int p;
    vector<int>sorsz;
};
map<int,vector<int> >csp;
vector<adat>x;
deque<int>q;
int akt;
bool jo;
int n, m, i, j, a, b,k,v;
void vissz(int csp)
{
    if (x[csp].honnan)
        vissz(x[csp].honnan);
    cout << csp << " ";
}
int mini = 9999,c;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n >> k >> v;
    x.resize(m + 1);
    for (i = 1; i <= m; ++i)
    {
        cin >> a;
        for (j = 1; j <= a; ++j)
        {
            cin >> b;
            if (k == b)
            {
                q.push_back(i);
                x[i].lat = true;
                x[i].lep = 1;
                x[i].kezd = 1;
                 
            }
            if (v == b)
            {
                x[i].veg = 1;
                       
            }
            if (csp[b].empty())
            {
                csp[b].push_back(i);
            }
            else if(!csp[b].empty())
            {
                for (auto& e : csp[b])
                {
                    x[i].sz.insert(e);
                    x[e].sz.insert(i);
                }
            }
        }
    }
    for (i = 1; i <= m; ++i)
    {
        if (x[i].kezd && x[i].veg)
        {
            cout << 1 << "\n" << i;
            return 0;
        }
    }
    while (!q.empty())
    {
        akt = q.front();
        q.pop_front();
        
        for (auto& e : x[akt].sz)
        {
            if (!x[e].lat)
            {
                if(!x[akt].veg)
                    q.push_back(e);
                x[e].lep = x[akt].lep + 1;
                x[e].honnan = akt;
                x[e].lat = true;
                if (x[e].veg)
                {
                    mini = x[e].lep;
                    c = e;
                }
            }
            else if (x[e].veg && x[e].lat)
            { 
                if (x[akt].lep + 1 < x[e].lep)
                {
                    x[e].honnan = akt;
                    mini = x[akt].lep + 1;
                    c = e;
                }
            }
        }
    }

    if (c)
    {   
        cout << mini << "\n";
        vissz(c);
    }
    else cout << -1;
    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

3 7 1 5
3 1 2 3
3 3 4 5
4 1 6 7 5

2 5 1 5
3 1 2 3
2 4 5
*/
// 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
base18/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/06ms1332 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms508 KiB
6Elfogadva2/21ms316 KiB
7Hibás válasz0/22ms580 KiB
8Elfogadva2/23ms564 KiB
9Hibás válasz0/24ms1076 KiB
10Hibás válasz0/24ms820 KiB
11Elfogadva2/22ms564 KiB
12Hibás válasz0/28ms1352 KiB
13Hibás válasz0/28ms1404 KiB
14Elfogadva2/26ms1324 KiB
15Hibás válasz0/2492ms1276 KiB
16Hibás válasz0/2488ms1204 KiB
17Hibás válasz0/2488ms1248 KiB
18Hibás válasz0/2490ms1276 KiB
19Elfogadva2/24ms1076 KiB
20Hibás válasz0/26ms1332 KiB
21Elfogadva2/23ms820 KiB
22Hibás válasz0/27ms1344 KiB