115162024-10-16 17:19:39chucknorrisA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 32/40363ms28252 KiB
#include <bits/stdc++.h>
#define INF 1e9

using namespace std;

int N, M, honnan, hova, n;
vector<pair<int, int> >L[10002];///allomas, vonal
int tmin[10002], t[10002];///tmin[i] = min metrok honnan - i; t[i] - melyik allomasrol ertem el az i-edik allomast min atszallassal
int v[10002];///v[i] = melyik vonalon erem el az i-edik allomast
int ans[10002];///a megoldas
priority_queue<pair<int, int> >q;

int main(){
    cin >> N >> M >> honnan >> hova;
    for(int i = 1; i <= N; i++){
        int x, y;
        cin >> n;///a vonal metrómegállóinak a száma
        cin >> x;///elso megálló
        for(int j = 1; j < n; j++){
            cin >> y;
            L[x].push_back({y, i});///x --> y az i-edik vonalon
            L[y].push_back({x, i});
            x = y;
        }
    }

    for(int i = 1; i <= M; i++) tmin[i] = INF;

    tmin[honnan] = 0; t[honnan] = 0; v[honnan] = 0;

    q.push({0, honnan});///a kezdo pontot a 0-dik vonalra teszem
    while(q.empty() == false){
        int x = q.top().second;
        int sz = -q.top().first;///minimum atszallasok x-ig
        int vonal = v[x];
        q.pop();
        for(int i = 0; i < L[x].size(); i++){
            int szomszed = L[x][i].first;
            int vonal1 = L[x][i].second;
            int atszall = tmin[x];
            if(vonal1 != vonal) atszall = atszall + 1;
            if(atszall < tmin[szomszed]){
                tmin[szomszed] = atszall; v[szomszed] = vonal1;
                t[szomszed] = x;
                q.push({-tmin[szomszed], szomszed});
            }
        }
    }

    if(tmin[hova] == INF){
        cout << "-1"; return 0;
    }

    cout << tmin[hova] << "\n";
    int stop = hova;
    stack<int>st;
    while(t[stop] > 0){
        ///cout << stop << " " << v[stop] << "\n";
        if(v[stop] != v[t[stop]]) st.push(v[stop]);///cout << "---" << v[stop] << "---\n";
        stop = t[stop];
    }
    while(st.empty() == false){
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/40
1Elfogadva0/01ms584 KiB
2Elfogadva0/07ms1092 KiB
3Elfogadva2/21ms584 KiB
4Elfogadva2/21ms580 KiB
5Elfogadva2/21ms672 KiB
6Elfogadva2/21ms660 KiB
7Elfogadva2/23ms672 KiB
8Elfogadva2/23ms848 KiB
9Elfogadva2/24ms896 KiB
10Hibás válasz0/24ms856 KiB
11Elfogadva2/22ms856 KiB
12Hibás válasz0/27ms1180 KiB
13Hibás válasz0/28ms1092 KiB
14Hibás válasz0/27ms1188 KiB
15Elfogadva2/2344ms28252 KiB
16Elfogadva2/2340ms28228 KiB
17Elfogadva2/2361ms28140 KiB
18Elfogadva2/2363ms28228 KiB
19Elfogadva2/24ms836 KiB
20Elfogadva2/26ms1156 KiB
21Elfogadva2/24ms832 KiB
22Elfogadva2/27ms1092 KiB