My BFS runs as follows. Reach all the nodes u can with normal paths. If final city is reached, break. Else add 1 to cost and reach all cities you can with a reverse path from current set of cities. Here’s the code: CodeChef: Practical coding for everyone
can someone tell me the mistake in my code. Algo that i used is same as the one given in editorial(using heaps) n i got WA.
can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible
and even if it is possible then how???
can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible and even if it is possible then how???
Maximum edges are given in the constraints: 10^5. Imagine the edges in terms of their costs. Travelling over a normal edge is 0. Inverting an edge has some cost, some constant value for all reverse edges. You can give it any value. The author has given all reverse edges a value of one because its simple to do so.
@adi_das >> for every given edge x->y, add it to the graph with weight 0 and also add a reverse edge y->x with weight 1. So if we are given E edges, after adding them and the reverse edges we will be having a total of 2*E edges, half of them with 0 weight and other half of them with weight 1. Hope this clarifies your doubt.
2 Likes
the limit is 10^6, you will exceed the memory constraint, the 2D array will not be formed.
In the tester’s solution, values are queued when their tentative distances are updated. This allows for the possibility of re-queuing verticies that are already in the queue. Why would we do this?
Use adj list instead of adj matrix , matrix will give TLE
Same here 
you can check my 0-1 bfs solution and dijkstra’s solution
" dijkstra’s" and “0-1” for correct implementations
1 Like
can someone please explain why am i getting WA in this _/_
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int INF = 1e9+10;
vector<pair<int,int>> g[N];
vector<int> lvl(N, INF);
void bfs(){
deque<int> q;
q.push_back(1);
lvl[1] = 0;
while(!q.empty()){
int curr = q.front();
q.pop_front();
for(auto edge : g[curr]){
int child_v = edge.first;
int wt = edge.second;
if(lvl[child_v] > lvl[curr] + wt){
lvl[child_v] = lvl[curr] + wt;
if(wt == 0){
q.push_front(edge.first);
}else{
q.push_back(edge.first);
}
}
}
}
}
int main(){
int m,n; cin>>n>>m;
for (int i = 0; i < m; ++i){
int v1,v2; cin>>v1>>v2;
if(v1==v2) continue;
g[v1].push_back({v2,0});
g[v2].push_back({v1,1});
}
bfs();
cout<<lvl[n]<<endl;
}