61192023-11-02 20:38:56MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Runtime error 6/5030ms64928 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    int n,m;
    cin >> m >>n;
    vector<int> adj[n];
    int vonalszam[n][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][j]=i+1;
            //cout << a << " " << j+1 << " " << vonalszam[a-1][j] << endl;
        }
    }
    queue<int>q;
    int votma[n] = {0};
    int elozo[n];
    int tav[n] = {0};
    q.push(0);
    votma[0]=1;
    elozo[0]=-1;
    while(!q.empty())
    {
        //cout << "!!1" << endl;
        int akt = q.front();
        q.pop();
        for(auto x : adj[akt])
        {
            if(votma[x]==0)
            {
                q.push(x);
                votma[x]=1;
                elozo[x]=akt;
                tav[x]=tav[akt]+1;
            }
        }
    }
    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 = 0; i < ut.size()-1; i++)
        cout << vonalszam[ut[i]][ut[i+1]] << " ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base6/50
1Accepted0/03ms2084 KiB
2Runtime error0/027ms64928 KiB
3Accepted1/13ms2164 KiB
4Accepted1/13ms2404 KiB
5Accepted2/23ms2608 KiB
6Accepted2/23ms2692 KiB
7Runtime error0/227ms64248 KiB
8Runtime error0/227ms64204 KiB
9Runtime error0/226ms63952 KiB
10Runtime error0/230ms63908 KiB
11Runtime error0/226ms63652 KiB
12Runtime error0/225ms63400 KiB
13Runtime error0/225ms63396 KiB
14Runtime error0/230ms63144 KiB
15Runtime error0/229ms63140 KiB
16Runtime error0/229ms63112 KiB
17Runtime error0/229ms62856 KiB
18Runtime error0/226ms62848 KiB
19Runtime error0/226ms62836 KiB
20Runtime error0/226ms62836 KiB
21Runtime error0/225ms62672 KiB
22Runtime error0/229ms62508 KiB
23Runtime error0/226ms62488 KiB
24Runtime error0/229ms62496 KiB
25Runtime error0/229ms62496 KiB
26Runtime error0/229ms62484 KiB
27Runtime error0/229ms62260 KiB
28Runtime error0/229ms62188 KiB