9488 | 2024. 02. 22 11:31:59 | Vkrisztian01 | A lehető legkevesebb metróval utazás (40 pont) | cpp11 | Elfogadva 40/40 | 126ms | 25356 KiB |
#include <iostream>
#include<vector>
#include<queue>
using namespace std;
int metro,allomas,start,finish,a,b,node;
vector<vector<int> > vonalak;
vector<vector<int> > allomasok;
vector<bool>hasznaltmetro;
vector<pair<int,int> > honnan;
queue<int>seged;
vector<int>ki;
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin>>metro>>allomas>>start>>finish;
vonalak.resize(metro+1);
allomasok.resize(allomas+1);
honnan.assign(allomas+1,make_pair(-1,-1));
hasznaltmetro.assign(metro+1,false);
for(int i=1;i<=metro;i++)
{
cin>>a;
while(a--)
{
cin>>b;
vonalak[i].push_back(b);
allomasok[b].push_back(i);
}
}
seged.push(start);
honnan[start]=make_pair(0,0);
while(!seged.empty())
{
node=seged.front();
seged.pop();
if(node==finish) break;
for(auto me:allomasok[node])
{
if(hasznaltmetro[me]) continue;
hasznaltmetro[me]=true;
for(auto celallomas:vonalak[me])
{
if(honnan[celallomas].first!=-1) continue;
honnan[celallomas]=make_pair(node,me);
seged.push(celallomas);
}
}
}
if(honnan[finish].first==-1)
{
cout<<-1;
return 0;
}
while(finish!=start)
{
ki.push_back(honnan[finish].second);
finish=honnan[finish].first;
}
cout<<ki.size()<<endl;
for(int i=ki.size()-1;i>=0;i--) cout<<ki[i]<<" ";
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1824 KiB | |||
2 | Elfogadva | 0/0 | 4ms | 3400 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2268 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2448 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2752 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2756 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3280 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3708 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3920 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3980 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 3512 KiB | |||
12 | Elfogadva | 2/2 | 4ms | 4636 KiB | |||
13 | Elfogadva | 2/2 | 6ms | 4688 KiB | |||
14 | Elfogadva | 2/2 | 4ms | 4836 KiB | |||
15 | Elfogadva | 2/2 | 122ms | 24760 KiB | |||
16 | Elfogadva | 2/2 | 126ms | 24920 KiB | |||
17 | Elfogadva | 2/2 | 126ms | 24984 KiB | |||
18 | Elfogadva | 2/2 | 122ms | 25356 KiB | |||
19 | Elfogadva | 2/2 | 4ms | 4472 KiB | |||
20 | Elfogadva | 2/2 | 4ms | 4768 KiB | |||
21 | Elfogadva | 2/2 | 4ms | 4120 KiB | |||
22 | Elfogadva | 2/2 | 4ms | 4836 KiB |