61282023-11-02 22:15:52MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Wrong answer 14/5079ms62632 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,m;
    cin >> n>>m;
    vector<pair<int,int>>jaratok;
    vector<int>szam;
    vector<int> adj[n];
    for(int i = 0; i < n; i++)
    {
        int a,b;
        cin >> a >> b;
        //cout << jaratok.size() << endl;
        for(int j = 0; j < jaratok.size(); j++)
        {
            int elso = jaratok[j].first;
            int utolso = jaratok[j].second;
            //cout << elso << " " << utolso << endl;
            if(a-1 >= elso && a-1 <= utolso)
            {
                adj[j].push_back(i);
                //adj[i].push_back(j);
                //cout  << i<< " " << j << endl;
            }
        }
        //cout << endl;
        jaratok.push_back(make_pair(a-1,b-1));
        //szam.push_back(i+1);
    }
    int votma[n] = {0};
    int elozo[n];
    elozo[0]=-1;
    queue<int>q;
    q.push(0);
    votma[0]=1;
    int utolso = -1;
    bool vanu = false;
    while(!q.empty())
    {
        int akt = q.front();
        q.pop();
        for(auto x : adj[akt])
        {
            if(votma[x]==0)
            {
                q.push(x);
                votma[x]=1;
                elozo[x]=akt;
                if(jaratok[x].second==m-1 && !vanu)
                {
                    //cout << x << " "
                    vanu = true;
                    utolso = x;
                }
                //cout << akt << " " << x << endl;
            }
        }

    }
    if(utolso==-1)
    {
        cout << -1;
        return 0;
    }
    //cout << utolso << endl;
    int uthossz = 0;
    vector<int>ut;
    int x = utolso;
    while(x!=-1)
    {
        ut.insert(ut.begin(),x);
        x = elozo[x];
        uthossz++;
    }
    cout << uthossz-1 << endl;
    sort(ut.begin(),ut.end());
    for(int i = 0; i < ut.size(); i++)
        cout << ut[i]+1 << " ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base14/50
1Accepted0/03ms2088 KiB
2Accepted0/064ms6304 KiB
3Accepted1/13ms2496 KiB
4Accepted1/13ms2628 KiB
5Wrong answer0/23ms2848 KiB
6Accepted2/23ms2832 KiB
7Accepted2/24ms3636 KiB
8Accepted2/26ms4404 KiB
9Wrong answer0/28ms4860 KiB
10Wrong answer0/212ms5624 KiB
11Wrong answer0/214ms5228 KiB
12Wrong answer0/221ms6016 KiB
13Wrong answer0/24ms4020 KiB
14Accepted2/27ms4408 KiB
15Wrong answer0/29ms5072 KiB
16Accepted2/220ms6396 KiB
17Wrong answer0/235ms6996 KiB
18Wrong answer0/243ms7848 KiB
19Wrong answer0/250ms8032 KiB
20Wrong answer0/252ms8160 KiB
21Wrong answer0/263ms8784 KiB
22Accepted2/264ms9100 KiB
23Runtime error0/279ms62632 KiB
24Runtime error0/271ms62608 KiB
25Runtime error0/278ms62372 KiB
26Runtime error0/271ms62340 KiB
27Runtime error0/276ms62176 KiB
28Runtime error0/278ms62148 KiB