I am doing standard BFS, and then finding the max of all min over all shortest paths

#include <bits/stdc++.h>(ignore this)
using namespace std;

void solve() {
    int n;
    int m;
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    for(int i=0;i<m;i++){
        int a;
        int b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<bool> vis(n+1,false);
    int s;
    int f;
    int r;
    cin >> s >> f >> r;
    vector<int> ds(n+1,0);
    vector<int> dr(n+1,0);
    //BFS from s
    queue<pair<int,int>> q;
    q.push({0,s});
    ds[s] = 0;
    while(!q.empty()){
        pair<int,int> v = q.front();
        q.pop();
        for(int j : adj[v.second]){
            if(vis[j] == false){
                ds[j] = v.first+1;
                vis[j] = true;
                q.push({ds[j],j});
            }
        }
    }
    for(int i=1;i<=n;i++){
        vis[i] = false;
    }
    // BFS from r
    q.push({0,r});
    dr[r] = 0;
    while(!q.empty()){
        pair<int,int> v = q.front();
        q.pop();
        for(int j : adj[v.second]){
            if(vis[j] == false){
                dr[j] = v.first+1;
                vis[j] = true;
                q.push({dr[j],j});
            }
        }
    }
    for(int i=1;i<=n;i++){
        vis[i] = false;
    }
    if(s == f){
        cout << dr[s] << endl;
        return;
    }
    int ans = -1;
    // Final BFS
    q.push({dr[s],s});
    bool found_f = false;
    while(!found_f){
        int k = q.size();
        while(k--){
            pair<int,int> v = q.front();
            q.pop();
            for(int j : adj[v.second]){
                q.push({min(dr[j],v.first),j});
                if(j == f){
                    found_f = true;
                }
            }
        }
    }
    int k = q.size();
    while(k--){
        pair<int,int> v = q.front();
        q.pop();
        if(v.second == f) ans = max(ans,v.first);
    }
    cout << ans << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Edited by author 09.07.2025 00:48