240932026-02-04 10:51:17ercseferencA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 38/40312ms11252 KiB
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //ifstream f("szamok.txt");
    int n,m,kezd,veg;
    cin>>n>>m>>kezd>>veg;
    vector<vector<int>>a(n+m+1);
    for(int i=1; i<=n; i++){
        int x; cin>>x;
        for(int j=0; j<x; j++){
            int y; cin>>y;
            a[y].push_back(m+i);
            a[m+i].push_back(y);}}
    vector<int>tav(n+m+1,1e9);
    vector<int>ut(n+m+1);
    queue<int>q;
    q.push(kezd);
    tav[kezd]=0;
    while(!q.empty()){
        int x=q.front();
        for(int i:a[x]){
            if(tav[i]>tav[x]+1){
                tav[i]=tav[x]+1;
                q.push(i);
                ut[i]=x;}}
        q.pop();}
    vector<int>nyom;
    if(tav[veg]==1e9){
        cout<<-1;}
    else{
        int t=veg;
        while(t!=kezd){
            t=ut[t];
            if(t>m)nyom.push_back(t-m);}
        reverse(nyom.begin(), nyom.end());}
    cout<<nyom.size()<<endl;
    for(int i:nyom)cout<<i<<" ";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base38/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/06ms1084 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Elfogadva2/22ms564 KiB
8Elfogadva2/22ms580 KiB
9Elfogadva2/24ms832 KiB
10Elfogadva2/24ms644 KiB
11Elfogadva2/22ms508 KiB
12Elfogadva2/27ms1064 KiB
13Elfogadva2/27ms924 KiB
14Elfogadva2/26ms1076 KiB
15Elfogadva2/2312ms11104 KiB
16Elfogadva2/2312ms11252 KiB
17Elfogadva2/2310ms11164 KiB
18Elfogadva2/2310ms11120 KiB
19Elfogadva2/24ms820 KiB
20Elfogadva2/26ms820 KiB
21Elfogadva2/23ms564 KiB
22Elfogadva2/26ms1008 KiB