48772023-04-05 20:31:59CWMA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40127ms26292 KiB
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <queue>

//upper bound >
//lower bound >=
//int index = (lower_bound(testvec.begin(), testvec.end(), num)-testvec.begin());

using namespace std;
using ll = long long;
int mod = 1000000007;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, length, start, end;
    cin >> n >> length >> start >> end;
    vector<vector<int>> railways(n);
    unordered_set<int> usedRailways;
    vector<int> dist(length+1,-1);
    vector<vector<int>> connectedRailways(length+1);
    queue<int> ToCheck;
    vector<pair<int,int>> From(length + 1); //From?, using which railway?
    for (size_t i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        for (size_t j = 0; j < a; j++)
        {
            int b; 
            cin >> b;
            railways[i].push_back(b);
            connectedRailways[b].push_back(i);
        }
    }
    From[start] = { -1,-1 };
    ToCheck.push(start);
    dist[start] = 0;
    while (usedRailways.size() != n && !ToCheck.empty()) {
        int curCheck = ToCheck.front();
        for (size_t i = 0; i < connectedRailways[curCheck].size(); i++)
        {
            if (usedRailways.count(connectedRailways[curCheck][i]) == 0) {
                int curRail = connectedRailways[curCheck][i];
                for (size_t i = 0; i < railways[curRail].size(); i++)
                {
                    if (dist[railways[curRail][i]] == -1) {
                        dist[railways[curRail][i]] = dist[curCheck] + 1;
                        From[railways[curRail][i]] = { curCheck,curRail };
                        ToCheck.push(railways[curRail][i]);
                    }
                }
                usedRailways.insert(curRail);
            }
        }
        ToCheck.pop();
    }
    if (dist[end] == -1) {
        cout << "-1";
        return 0;
    }
    cout << dist[end] << "\n";
    vector<int> endFrom;
    pair<int, int> cur = From[end];
    while (cur.second!=-1) {
        endFrom.push_back(cur.second);
        cur = From[cur.first];
    }
    for (size_t i = 0; i < endFrom.size(); i++)
    {
        cout << endFrom[endFrom.size() - i - 1]+1 << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/03ms1824 KiB
2Elfogadva0/04ms3388 KiB
3Elfogadva2/23ms2140 KiB
4Elfogadva2/23ms2336 KiB
5Elfogadva2/23ms2628 KiB
6Elfogadva2/22ms2644 KiB
7Elfogadva2/23ms3192 KiB
8Elfogadva2/23ms3464 KiB
9Elfogadva2/24ms4024 KiB
10Elfogadva2/24ms4212 KiB
11Elfogadva2/23ms4064 KiB
12Elfogadva2/26ms5056 KiB
13Elfogadva2/24ms5060 KiB
14Elfogadva2/24ms5268 KiB
15Elfogadva2/2127ms26156 KiB
16Elfogadva2/2127ms25696 KiB
17Elfogadva2/2125ms25628 KiB
18Elfogadva2/2125ms26292 KiB
19Elfogadva2/24ms5312 KiB
20Elfogadva2/24ms5752 KiB
21Elfogadva2/24ms5232 KiB
22Elfogadva2/24ms5868 KiB