4877 2023. 04. 05 20:31:59 CWM A lehető legkevesebb metróval utazás (40 pont) cpp17 Elfogadva 40/40 127ms 26292 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 Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1824 KiB
2 Elfogadva 0/0 4ms 3388 KiB
3 Elfogadva 2/2 3ms 2140 KiB
4 Elfogadva 2/2 3ms 2336 KiB
5 Elfogadva 2/2 3ms 2628 KiB
6 Elfogadva 2/2 2ms 2644 KiB
7 Elfogadva 2/2 3ms 3192 KiB
8 Elfogadva 2/2 3ms 3464 KiB
9 Elfogadva 2/2 4ms 4024 KiB
10 Elfogadva 2/2 4ms 4212 KiB
11 Elfogadva 2/2 3ms 4064 KiB
12 Elfogadva 2/2 6ms 5056 KiB
13 Elfogadva 2/2 4ms 5060 KiB
14 Elfogadva 2/2 4ms 5268 KiB
15 Elfogadva 2/2 127ms 26156 KiB
16 Elfogadva 2/2 127ms 25696 KiB
17 Elfogadva 2/2 125ms 25628 KiB
18 Elfogadva 2/2 125ms 26292 KiB
19 Elfogadva 2/2 4ms 5312 KiB
20 Elfogadva 2/2 4ms 5752 KiB
21 Elfogadva 2/2 4ms 5232 KiB
22 Elfogadva 2/2 4ms 5868 KiB