133012025-01-07 12:52:16ercseferencA lehető legkevesebb átszállás (50 pont)cpp17Elfogadva 50/5010ms2356 KiB
#include <bits/stdc++.h>
using namespace std;
struct kisvonat{int bem,kim,ind;};
struct vonat{vector<int>kime,his; int kim,bem,ind; bool van=0;};
bool hasonl(kisvonat n, kisvonat m){
    if(n.bem==m.bem)return n.kim>m.kim;
    else return n.bem<m.bem;}
int main()
{
    int n,m; cin>>n>>m;
    vector<kisvonat>kis(n); vector<vonat>a;
    for(int i=0; i<n; i++){cin>>kis[i].bem>>kis[i].kim; kis[i].ind=i+1;}
    sort(kis.begin(),kis.end(),hasonl);
    int maxi=0;
    for(int i=0; i<n; i++){
        if(maxi<kis[i].kim){maxi=kis[i].kim; vonat x; x.ind=kis[i].ind;
        x.kim=kis[i].kim; x.bem=kis[i].bem; a.push_back(x);}}
    int ker=a.size(); vonat x; x.bem=m; x.kim=-1; x.ind=-1; a.push_back(x);
    for(int i=0; i<ker; i++){int k=i+1;
        while(a[k].bem<=a[i].kim && k<=ker){
            a[i].kime.push_back(k); k++;}}
    int k=0; vector<int>l1,l2; bool nincs=0;
    if(a[0].bem==1){l1.push_back(0); a[0].van=1;}
    a[0].his.push_back(a[0].ind);
    while(!nincs){
        for(int i=0; i<l1.size(); i++){
            for(int j=0; j<a[l1[i]].kime.size(); j++){
                if(a[a[l1[i]].kime[j]].van==0){
                    a[a[l1[i]].kime[j]].van=1;
                    a[a[l1[i]].kime[j]].his=a[l1[i]].his;
                    a[a[l1[i]].kime[j]].his.push_back(a[a[l1[i]].kime[j]].ind);
                    l2.push_back(a[l1[i]].kime[j]);}}}
        if(l2.size()==0)nincs=1;
        l1.clear(); l1=l2; l2.clear();}
    if(!a[ker].van)cout<<-1;
    else {
        cout<<a[ker].his.size()-2<<endl;
        for(int i=0; i<a[ker].his.size()-1; i++){cout<<a[ker].his[i]<<" ";}}
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms500 KiB
2Elfogadva0/010ms2356 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms380 KiB
7Elfogadva2/22ms412 KiB
8Elfogadva2/22ms544 KiB
9Elfogadva2/22ms316 KiB
10Elfogadva2/23ms316 KiB
11Elfogadva2/24ms700 KiB
12Elfogadva2/24ms820 KiB
13Elfogadva2/22ms316 KiB
14Elfogadva2/23ms680 KiB
15Elfogadva2/24ms820 KiB
16Elfogadva2/24ms820 KiB
17Elfogadva2/28ms1612 KiB
18Elfogadva2/28ms1784 KiB
19Elfogadva2/28ms2056 KiB
20Elfogadva2/29ms2292 KiB
21Elfogadva2/29ms2356 KiB
22Elfogadva2/29ms2356 KiB
23Elfogadva2/28ms512 KiB
24Elfogadva2/28ms516 KiB
25Elfogadva2/28ms516 KiB
26Elfogadva2/28ms316 KiB
27Elfogadva2/28ms516 KiB
28Elfogadva2/28ms316 KiB