ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 2034. Caravans

WA 32 ...why this method is wrong
Posted by Sagar Goyal 8 Aug 2022 14:41
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();

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

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

for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
}

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

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;
}
Re: WA 32 ...why this method is wrong
Posted by AmEr 17 Aug 2022 04:41
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
Re: WA 32 ...why this method is wrong
Posted by evjava 12 Dec 2022 03:21
Consider this test:

9 12
1 2
1 3
2 4
2 5
3 6
3 7
4 6
4 9
5 6
6 8
7 8
7 9
1 9 6