61212023-11-02 21:12:42MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Runtime error 32/5054ms64828 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    int n,m;
    cin >> m >>n;
    vector<int> adj[n];
    vector<int> vonalszam[n];
    for(int i = 0; i < m; i++)
    {
        int a,b;
        cin >> a >> b;
        for(int j = a; j < b; j++)
        {
            adj[a-1].push_back(j);
            vonalszam[a-1].push_back(i+1);
            //cout << a << " " << j+1 << " " << i+1 << endl;
        }
    }
    queue<int>q;
    int votma[n] = {0};
    int elozo[n];
    elozo[n-1]=-1;
    int vonal[n];
    int tav[n] = {0};
    q.push(0);
    votma[0]=1;
    elozo[0]=-1;
    while(!q.empty())
    {
        int akt = q.front();
        q.pop();
        int k = 0;
        for(auto x : adj[akt])
        {
            if(votma[x]==0)
            {
                q.push(x);
                votma[x]=1;
                elozo[x]=akt;
                tav[x]=tav[akt]+1;
                vonal[x]= *(vonalszam[akt].begin()+k);
                //cout << akt << " " << x << " " << *(vonalszam[akt].begin()+k) << endl;
            }
            k++;
        }
    }
    if(elozo[n-1]==-1)
    {
        cout << -1;
        return 0;
    }
    cout << tav[n-1]-1<< endl;
    vector<int>ut;
    int x = n-1;
    while(x!=-1)
    {
        ut.insert(ut.begin(),x);
        x = elozo[x];
    }
    for(int i = 1; i < ut.size(); i++)
        cout << vonal[ut[i]] << " ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base32/50
1Accepted0/03ms1936 KiB
2Runtime error0/050ms64828 KiB
3Accepted1/13ms2408 KiB
4Accepted1/13ms2556 KiB
5Accepted2/23ms2776 KiB
6Accepted2/23ms2936 KiB
7Accepted2/28ms9244 KiB
8Accepted2/29ms12016 KiB
9Accepted2/212ms15164 KiB
10Accepted2/217ms21760 KiB
11Accepted2/225ms29940 KiB
12Accepted2/228ms35644 KiB
13Accepted2/28ms11512 KiB
14Accepted2/214ms19292 KiB
15Accepted2/219ms26212 KiB
16Accepted2/228ms37604 KiB
17Accepted2/245ms52376 KiB
18Accepted2/250ms58212 KiB
19Accepted2/254ms62592 KiB
20Runtime error0/252ms63012 KiB
21Runtime error0/248ms62776 KiB
22Runtime error0/246ms62748 KiB
23Runtime error0/248ms62708 KiB
24Runtime error0/252ms62684 KiB
25Runtime error0/250ms62680 KiB
26Runtime error0/241ms62660 KiB
27Runtime error0/248ms62656 KiB
28Runtime error0/250ms62636 KiB