Out of all shortest path I am finding min of maximum distance I have to travel for every level.





#include<bits/stdc++.h>
using namespace std;

void bfs(int u,vector<int> &d,const vector<vector<int>> adj){
    d[u] = 0;
    queue<int> q;
    q.push(u);

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

        for(auto v:adj[u]){
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n);

    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }

    vector<int> ds(n,1e9),df(n,1e9),dr(n,1e9);
    int s,f,r;
    cin>>s>>f>>r;
    s--,f--,r--;
    bfs(s,ds,adj);
    bfs(f,df,adj);
    bfs(r,dr,adj);

    vector<vector<int>> l(ds[f]+1);

    for(int i=0;i<n;i++){
        if(ds[i]+df[i]==ds[f]){
            l[ds[i]].push_back(i);
        }
    }
    int ans = INT_MAX;
    for(int i=0;i<=ds[f];i++){
        int a = INT_MIN;
        for(auto x: l[i]){
            a = max(a,dr[x]);
        }
        ans = min(a,ans);
    }

    cout<<ans;

    return 0;
}

Why

6 6
1 2
2 3
3 4
4 5
1 6
6 5
1 5 6
ans : 0

For this Test case , AC solution gives output 2 which should be 1.

25 28
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1
5 19
19 20
20 21
21 22
22 23
23 24
24 25
25 14
15 22
6 22
1 10 22

Edited by author 20.02.2020 05:33

Edited by author 20.02.2020 05:33

I figured out that n == 8 in test 2.
It may be useful for somebody.

I run 2 bfs. The first bfs starting from node S (that is caravan's distances) and the second starting from node R (that's distances from robbers). Then i recover route for caravan and on each step backward i choose node with maximum robber distance. Minimum of robber distance on the caravans path is the answer. What's wrong?

Check that you use only shortest routes.
I don't have any tests, but when I started checking this, then I got ACC.

15 17
1 2
2 3
3 4
4 5
5 6
6 14
14 15
15 9
9 7
7 5
7 8
8 13
13 12
11 12
10 11
10 4
1 6
1 12 15
ans: 3

I checked two accepted solution But They are giving different output in same test case.
AC code 1:  https://paste.ubuntu.com/p/RwtFH2s4xK/
AC code 2:  https://paste.ubuntu.com/p/vmrXrdcJN6/

Tese case :
25 28
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1
5 19
19 20
20 21
21 22
22 23
23 24
24 25
25 14
15 22
6 22
1 10 21

Output in code 1 : 2
Output in code 2 : 3

Answer should be : 2

robbers dont know the path, so at each point take farthest node from robbers.do these fo for the length of shortest path and in the end take minimum of these.

My O(N * log N + M) solutions gets TL
What I'm doing wrong?

BinSearch.

Edited by author 14.07.2018 05:22

What is the second test case?

Passed all the test given in the discussion
I ran 1 bfs from 'r' and another bfs from 's' where i also kept data for those nodes who can have multiple parents.
than I while restoring path from destination to source I selected the node who has higher level from 'r' (that selection occurs if only the node has possibility multiple parents)
returned the ans which is the minimum among the final path

Kirill

I use bfs...but record the route in a map, and maybe the copy of the map cost too much time...
How can I get all the routes in another good way?

Does someone have any idea what's test 3?

The memory limit is terrible!
so small!

Increase it plz!!!

Edited by author 21.03.2015 14:43