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[u1].push_back(v1); adj[v1].push_back(u1); } 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; } This is wrong because you're assuming that the answer is the minimum distance to the robbers in its unique optimal path, which is not always true. Edited by author 17.08.2022 04:41 Edited by author 17.08.2022 04:41 6 6 1 2 2 3 3 4 4 5 1 6 6 5 1 5 6 ans : 0 oh,no!my answer is 0 but WA in test 8...... Answer is 1 Actually it's 0. We should stay in 6, since there is only 1 shortest path. I have an another test case: 8 8 1 2 1 6 2 4 6 7 3 4 4 5 7 8 5 8 1 8 3 Answer: 3 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 is 1 the correct answer ? Nvm Edited by author 23.09.2020 15:53 I figured out that n == 8 in test 2. It may be useful for somebody. I got my problem I erased from multiset in a wrong way what is the whole test case ? . i am getting wrong answer on test case 2 ! 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? It's because you can't greedily choose the node with the maximum robber distance. One of the other paths might contain a node with a smaller node distance somewhere further along. One such graph is here (this one is rather long, you probably just want to try to generate a graph that violates your greedy strategy yourself): 15 20 1 2 2 4 4 6 6 8 1 3 3 5 5 7 7 6 4 5 2 3 7 8 7 9 9 10 10 11 11 12 12 6 11 14 14 13 13 15 15 3 1 8 11 One strategy that works is to BFS backwards from the finishing vertex, and along each path you maintain the minimum robber distance. When two (or more) paths merge on some vertex, you consider the minimum of this path to be the maximum of the minimums of the two paths. Otrebus, thank you for strategy ! what will be the ans of this case, could you tell me please??? 3? i am also getting 3 for this case but wrong answer on test case #2 .. 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 @Aristarch I also get 3 as ans. But , still getting WA in test case 13. 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? Have somebody any tests? please! 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 Just invent some algorithm and prove your algorithm is correct That is prove that your algorithm finds the answer I remember initially my algorithm was correct but consumed too much memory So final algorithm was different Kirill Where did you see it before? 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 
