240912026-02-04 10:07:13ercseferencA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 28/40601ms12224 KiB
#include <bits/stdc++.h>
using namespace std;
struct vonat{vector<int>ut; set<int>kim; bool volt=0;};
int main()
{
    //ifstream f("szamok.txt");
    int n,m,kezd,veg;
    cin>>n>>m>>kezd>>veg;
    vector<vonat>a(n+1);
    vector<vector<int>>meg(m+1);
    for(int i=1; i<=n; i++){
        int x; cin>>x;
        for(int j=0; j<x; j++){
            int y; cin>>y;
            meg[y].push_back(i);}}
    for(int i=1; i<=m; i++){
        for(int j=0; j<meg[i].size(); j++)
            for(int k=j+1; k<meg[i].size(); k++){
                int t1=meg[i][j];
                int t2=meg[i][k];
                a[t1].kim.insert(t2);
                a[t2].kim.insert(t1);}}
    set<int>kezdo;
    set<int>vegso;
    for(int i:meg[kezd])kezdo.insert(i);
    for(int i:meg[veg])vegso.insert(i);
    vector<int>mini;
    for(int i:kezdo){
        for(int j=1; j<=n; j++){
            a[j].ut.clear(); a[j].volt=0;}
        queue<int>q;
        int megold=-1;
        q.push(i);
        a[i].volt=1;
        a[i].ut.push_back(i);
        bool mehet=1;
        while(!q.empty() && mehet){
            int x=q.front();
            for(int j:a[x].kim){
                if(!a[j].volt){
                    a[j].volt=1;
                    a[j].ut=a[x].ut;//utadas
                    a[j].ut.push_back(j);//utadas
                    if(vegso.count(j)){megold=j; mehet=0;}//leallitas
                    q.push(j);}}
            q.pop();}
            if(megold==-1)continue;
            else if(mini.size()==0)mini=a[megold].ut;
            else if(mini.size()>a[megold].ut.size())
                mini=a[megold].ut;}
    if(mini.size()==0)cout<<-1;
    else {
        cout<<mini.size()<<endl;
        for(int i:mini)cout<<i<<" ";}
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/07ms1076 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms500 KiB
5Hibás válasz0/21ms316 KiB
6Elfogadva2/21ms508 KiB
7Elfogadva2/22ms344 KiB
8Elfogadva2/22ms564 KiB
9Elfogadva2/24ms644 KiB
10Elfogadva2/24ms576 KiB
11Elfogadva2/22ms316 KiB
12Elfogadva2/27ms880 KiB
13Elfogadva2/27ms1032 KiB
14Elfogadva2/27ms1076 KiB
15Időlimit túllépés0/2600ms11268 KiB
16Időlimit túllépés0/2600ms12224 KiB
17Időlimit túllépés0/2600ms7516 KiB
18Időlimit túllépés0/2601ms7516 KiB
19Elfogadva2/24ms820 KiB
20Elfogadva2/27ms820 KiB
21Elfogadva2/23ms564 KiB
22Elfogadva2/27ms1076 KiB