240922026-02-04 10:14:10ercseferencA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 28/40601ms7584 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(a[j].ut.size()>=mini.size() && !mini.empty())mehet=0;
                    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/01ms344 KiB
2Elfogadva0/07ms1076 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Hibás válasz0/21ms384 KiB
6Elfogadva2/21ms400 KiB
7Elfogadva2/22ms316 KiB
8Elfogadva2/22ms364 KiB
9Elfogadva2/24ms636 KiB
10Elfogadva2/24ms544 KiB
11Elfogadva2/23ms536 KiB
12Elfogadva2/27ms1048 KiB
13Elfogadva2/27ms924 KiB
14Elfogadva2/26ms1052 KiB
15Időlimit túllépés0/2601ms7476 KiB
16Időlimit túllépés0/2600ms7576 KiB
17Időlimit túllépés0/2600ms7560 KiB
18Időlimit túllépés0/2600ms7584 KiB
19Elfogadva2/24ms856 KiB
20Elfogadva2/27ms1004 KiB
21Elfogadva2/24ms800 KiB
22Elfogadva2/28ms1084 KiB