61272023-11-02 22:06:19MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base14/50
1Elfogadva0/03ms1812 KiB
2Elfogadva0/064ms6008 KiB
3Elfogadva1/13ms2380 KiB
4Elfogadva1/13ms2616 KiB
5Hibás válasz0/23ms2736 KiB
6Elfogadva2/23ms2908 KiB
7Elfogadva2/24ms3788 KiB
8Elfogadva2/26ms4612 KiB
9Hibás válasz0/28ms4840 KiB
10Hibás válasz0/210ms5588 KiB
11Hibás válasz0/214ms5192 KiB
12Hibás válasz0/220ms5976 KiB
13Hibás válasz0/24ms4012 KiB
14Elfogadva2/27ms4396 KiB
15Hibás válasz0/29ms4804 KiB
16Elfogadva2/221ms6148 KiB
17Hibás válasz0/235ms6644 KiB
18Hibás válasz0/243ms7388 KiB
19Hibás válasz0/250ms7728 KiB
20Hibás válasz0/252ms7720 KiB
21Hibás válasz0/263ms8464 KiB
22Elfogadva2/264ms8784 KiB
23Futási hiba0/281ms62884 KiB
24Futási hiba0/279ms62644 KiB
25Futási hiba0/279ms62404 KiB
26Futási hiba0/279ms62380 KiB
27Futási hiba0/278ms62372 KiB
28Futási hiba0/271ms62344 KiB