61192023-11-02 20:38:56MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base6/50
1Elfogadva0/03ms2084 KiB
2Futási hiba0/027ms64928 KiB
3Elfogadva1/13ms2164 KiB
4Elfogadva1/13ms2404 KiB
5Elfogadva2/23ms2608 KiB
6Elfogadva2/23ms2692 KiB
7Futási hiba0/227ms64248 KiB
8Futási hiba0/227ms64204 KiB
9Futási hiba0/226ms63952 KiB
10Futási hiba0/230ms63908 KiB
11Futási hiba0/226ms63652 KiB
12Futási hiba0/225ms63400 KiB
13Futási hiba0/225ms63396 KiB
14Futási hiba0/230ms63144 KiB
15Futási hiba0/229ms63140 KiB
16Futási hiba0/229ms63112 KiB
17Futási hiba0/229ms62856 KiB
18Futási hiba0/226ms62848 KiB
19Futási hiba0/226ms62836 KiB
20Futási hiba0/226ms62836 KiB
21Futási hiba0/225ms62672 KiB
22Futási hiba0/229ms62508 KiB
23Futási hiba0/226ms62488 KiB
24Futási hiba0/229ms62496 KiB
25Futási hiba0/229ms62496 KiB
26Futási hiba0/229ms62484 KiB
27Futási hiba0/229ms62260 KiB
28Futási hiba0/229ms62188 KiB