50482023-04-11 20:18:54CattA lehető legkevesebb átszállás (50 pont)cpp17Wrong answer 2/5013ms11520 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9; // Infinite distance value

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(m+1); // Adjacency list
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(i); // Add train to adjacency list of starting station
        adj[b].push_back(-i); // Add train (with negative index) to adjacency list of ending station
    }

    vector<int> dist(m+1, INF); // Initialize distance array with infinite distance
    vector<int> prev(m+1, -1); // Initialize previous node array with -1
    queue<int> q;

    dist[1] = 0; // Starting station has 0 distance
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            int w = 1; // Weight of edge is 1, since it represents changing trains
            if (v < 0) { // If v is a train arriving at the ending station
                v = -v; // Get the index of the train
                w = 0; // The weight of the edge is 0, since the train is already at the ending station
            }
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                q.push(v);
            }
        }
    }

    if (dist[m] == INF) {
        cout << -1 << endl; // If it is not possible to reach the ending station
    } else {
        cout << dist[m] << endl; // Minimum number of changes to reach the ending station
        vector<int> path;
        int u = m;
        while (u != -1) { // Reconstruct the path from the ending station to the starting station
            path.push_back(u);
            u = prev[u];
        }
        for (int i = path.size()-1; i >= 0; i--) {
            if (path[i] > 0) {
                cout << path[i] << " "; // Print the index of the train
            }
        }
        cout << endl;
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base2/50
1Wrong answer0/03ms1808 KiB
2Wrong answer0/013ms9328 KiB
3Accepted1/12ms2188 KiB
4Accepted1/12ms2424 KiB
5Wrong answer0/22ms2504 KiB
6Wrong answer0/22ms2708 KiB
7Wrong answer0/24ms3272 KiB
8Wrong answer0/24ms3348 KiB
9Wrong answer0/24ms3676 KiB
10Wrong answer0/24ms4300 KiB
11Wrong answer0/27ms6128 KiB
12Wrong answer0/28ms6412 KiB
13Wrong answer0/24ms4884 KiB
14Wrong answer0/24ms6084 KiB
15Wrong answer0/26ms6932 KiB
16Wrong answer0/28ms7072 KiB
17Wrong answer0/29ms9648 KiB
18Wrong answer0/210ms9848 KiB
19Wrong answer0/213ms10496 KiB
20Wrong answer0/213ms11100 KiB
21Wrong answer0/213ms11172 KiB
22Wrong answer0/213ms11300 KiB
23Wrong answer0/212ms9300 KiB
24Wrong answer0/212ms10348 KiB
25Wrong answer0/213ms10788 KiB
26Wrong answer0/213ms11440 KiB
27Wrong answer0/213ms11520 KiB
28Wrong answer0/213ms11520 KiB