Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
1.6 kB
8
Indexable
Never
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int bfs(const vector<vector<int>>& adj_list, int src, int dest) {
    vector<bool> visited(adj_list.size(), false);
    vector<int> distance(adj_list.size(), INT_MAX);

    queue<int> q;
    q.push(src);
    visited[src] = true;
    distance[src] = 0;

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

        for (int neighbor : adj_list[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[current] + 1;
                q.push(neighbor);
            }
        }
    }

    return distance[dest] == INT_MAX ? -1 : distance[dest];
}

int nearestMeetingCell(int N, const vector<int>& edges, int src, int dest) {
    vector<vector<int>> adj_list(N);

    for (int i = 0; i < N; ++i) {
        int next_node = edges[i];
        if (next_node != -1) {
            adj_list[i].push_back(next_node);
        }
    }

    int distance1 = bfs(adj_list, src, dest);
    int distance2 = bfs(adj_list, dest, src);

    if (distance1 == -1 || distance2 == -1) {
        return -1;
    }

    return min(distance1, distance2);
}

void solution_function() {
    int n;
    cin >> n;

    vector<int> edges(n);
    for (int i = 0; i < n; ++i) {
        cin >> edges[i];
    }

    int src, dest;
    cin >> src >> dest;

    int result = nearestMeetingCell(n, edges, src, dest);
    cout << result << endl;
}

int main() {
    solution_function();
    return 0;
}
Leave a Comment