9173 2024. 02. 16 19:30:39 mraron A lehető legkevesebb metróval utazás (40 pont) cpp17 Futási hiba 30/40 273ms 64156 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, start, end;
    cin >> n >> m >> start >> end;
    vector<vector<int>> metro(n);
    vector<vector<int>> adj(m + 1);
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        metro[i].resize(a);
        for (int j = 0; j < a; j++)
        {
            int b;
            cin >> b;
            adj[b].push_back(i);
            metro[i].push_back(b);
        }
    }
    priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> q;
    q.push({0, start, -2, -2});
    vector<int> dist(m + 1, INF);
    vector<pair<int, int>> parent(m + 1);
    while (!q.empty())
    {
        auto [d, v, p, met] = q.top();
        q.pop();
        if (dist[v] != INF)
        {
            continue;
        }
        dist[v] = d;
        parent[v] = {p, met};

        for (int i : adj[v])
        {
            for (int j : metro[i])
            {
                if (dist[j] > dist[v] + 1)
                {
                    array<int, 4> pb;
                    pb[0] = dist[v] + 1;
                    pb[1] = j;
                    pb[2] = v;
                    pb[3] = i;
                    q.push(pb);
                }
            }
        }
    }
    
    if (dist[end] == INF)
    {
        cout << "-1";
        return 0;
    }
    cout << dist[end] << "\n";
    vector<int> ans;
    while (true)
    {
        if(parent[end].second==-2) break;
        ans.push_back(parent[end].second);
        end = parent[end].first;
        
    }
    reverse(ans.begin(), ans.end());
    
    for (int i : ans)
        cout << i + 1 << " ";
}

Részfeladat Összpont Teszt Verdikt Idő Memória
base 30/40
1 Elfogadva 0/0 3ms 1752 KiB
2 Elfogadva 0/0 93ms 4788 KiB
3 Elfogadva 2/2 3ms 2068 KiB
4 Elfogadva 2/2 3ms 2116 KiB
5 Elfogadva 2/2 4ms 2912 KiB
6 Elfogadva 2/2 3ms 2468 KiB
7 Elfogadva 2/2 144ms 7088 KiB
8 Elfogadva 2/2 240ms 36264 KiB
9 Futási hiba 0/2 70ms 64156 KiB
10 Elfogadva 2/2 273ms 36656 KiB
11 Elfogadva 2/2 28ms 7684 KiB
12 Elfogadva 2/2 125ms 7048 KiB
13 Elfogadva 2/2 127ms 7024 KiB
14 Elfogadva 2/2 104ms 7204 KiB
15 Futási hiba 0/2 175ms 63432 KiB
16 Futási hiba 0/2 175ms 63456 KiB
17 Futási hiba 0/2 174ms 63428 KiB
18 Futási hiba 0/2 175ms 63336 KiB
19 Elfogadva 2/2 41ms 5052 KiB
20 Elfogadva 2/2 78ms 6068 KiB
21 Elfogadva 2/2 16ms 4676 KiB
22 Elfogadva 2/2 92ms 6480 KiB