61272023-11-02 22:06:19MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Wrong answer 14/5081ms62884 KiB
#include <iostream>
#include <queue>
#include <vector>
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;
    for(int i = 0; i < ut.size(); i++)
        cout << ut[i]+1 << " ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base14/50
1Accepted0/03ms1812 KiB
2Accepted0/064ms6008 KiB
3Accepted1/13ms2380 KiB
4Accepted1/13ms2616 KiB
5Wrong answer0/23ms2736 KiB
6Accepted2/23ms2908 KiB
7Accepted2/24ms3788 KiB
8Accepted2/26ms4612 KiB
9Wrong answer0/28ms4840 KiB
10Wrong answer0/210ms5588 KiB
11Wrong answer0/214ms5192 KiB
12Wrong answer0/220ms5976 KiB
13Wrong answer0/24ms4012 KiB
14Accepted2/27ms4396 KiB
15Wrong answer0/29ms4804 KiB
16Accepted2/221ms6148 KiB
17Wrong answer0/235ms6644 KiB
18Wrong answer0/243ms7388 KiB
19Wrong answer0/250ms7728 KiB
20Wrong answer0/252ms7720 KiB
21Wrong answer0/263ms8464 KiB
22Accepted2/264ms8784 KiB
23Runtime error0/281ms62884 KiB
24Runtime error0/279ms62644 KiB
25Runtime error0/279ms62404 KiB
26Runtime error0/279ms62380 KiB
27Runtime error0/278ms62372 KiB
28Runtime error0/271ms62344 KiB