61212023-11-02 21:12:42MrChipserA lehető legkevesebb átszállás (50 pont)cpp11Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/50
1Elfogadva0/03ms1936 KiB
2Futási hiba0/050ms64828 KiB
3Elfogadva1/13ms2408 KiB
4Elfogadva1/13ms2556 KiB
5Elfogadva2/23ms2776 KiB
6Elfogadva2/23ms2936 KiB
7Elfogadva2/28ms9244 KiB
8Elfogadva2/29ms12016 KiB
9Elfogadva2/212ms15164 KiB
10Elfogadva2/217ms21760 KiB
11Elfogadva2/225ms29940 KiB
12Elfogadva2/228ms35644 KiB
13Elfogadva2/28ms11512 KiB
14Elfogadva2/214ms19292 KiB
15Elfogadva2/219ms26212 KiB
16Elfogadva2/228ms37604 KiB
17Elfogadva2/245ms52376 KiB
18Elfogadva2/250ms58212 KiB
19Elfogadva2/254ms62592 KiB
20Futási hiba0/252ms63012 KiB
21Futási hiba0/248ms62776 KiB
22Futási hiba0/246ms62748 KiB
23Futási hiba0/248ms62708 KiB
24Futási hiba0/252ms62684 KiB
25Futási hiba0/250ms62680 KiB
26Futási hiba0/241ms62660 KiB
27Futási hiba0/248ms62656 KiB
28Futási hiba0/250ms62636 KiB