61252023-11-02 21:57:00MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Hibás válasz 12/50137ms63192 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;
    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;
            }
        }

    }
    //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
base12/50
1Elfogadva0/03ms1812 KiB
2Elfogadva0/0137ms9072 KiB
3Hibás válasz0/13ms2536 KiB
4Hibás válasz0/12ms2436 KiB
5Hibás válasz0/23ms2640 KiB
6Elfogadva2/22ms2620 KiB
7Elfogadva2/24ms3764 KiB
8Elfogadva2/28ms5080 KiB
9Hibás válasz0/210ms5820 KiB
10Hibás válasz0/218ms6936 KiB
11Hibás válasz0/228ms5648 KiB
12Hibás válasz0/241ms7204 KiB
13Hibás válasz0/24ms3712 KiB
14Elfogadva2/29ms4044 KiB
15Hibás válasz0/217ms4868 KiB
16Elfogadva2/241ms7224 KiB
17Hibás válasz0/271ms7980 KiB
18Hibás válasz0/290ms8968 KiB
19Hibás válasz0/2108ms9620 KiB
20Hibás válasz0/2114ms9828 KiB
21Hibás válasz0/2135ms11024 KiB
22Elfogadva2/2137ms11224 KiB
23Futási hiba0/257ms63192 KiB
24Futási hiba0/256ms62952 KiB
25Futási hiba0/256ms62676 KiB
26Futási hiba0/248ms62664 KiB
27Futási hiba0/248ms62440 KiB
28Futási hiba0/254ms62208 KiB