please help me. i have some problems in test 5. please help me! try this: 3 2 1 3 2 3 1 2 answear: 1 You realy snooze a lot my code have wrong in test5 and the ansear this test is correct:( Please do not waste the rest of your time Edited by author 25.07.2020 15:37 Edited by author 25.07.2020 15:37 can someone please provide test #6? I had maintained dis[n+1][2] for distance. But visited array was vis[n+1], changed it to vis[n+1][2] and simple bfs. This test helped me to find my bug. I modified dijkstra algo and added direction array. 9 12 7 3 9 3 9 2 1 2 1 3 4 7 4 1 5 1 4 8 5 8 6 5 2 6 1 8 Answer:0 Edited by author 31.01.2013 17:37 Thanks a lot! I was maintaining an array how[], which was storing how to get at that node (uphill mode or downhill node). But that failed Test case #11. I modified the code such that I start Dijkstra's algorithm at the destination node (Orlov's city) as the source node and Ivan's city as the target node. I actually interchanged source with end. So now I think my how[] array stores how one should get here. And it passed all test cases! Does this work because we have no limitation on how to start, but rather how we end makes more impact on the solution? I cannot derive a formal proof. Any comments are welcome #include<bits/stdc++.h> using namespace std; #define endl "\n" #define int long long #define mod 1000000007 #define maxn 10010 #define pb push_back #define mp make_pair #define fi first #define se second #define inf 100000000000 vector<pair<int, int>> adj[maxn]; int n, m; // struct node //for edges // { // int pos, dir, dist; // node(){}; // node(int _pos, int _dir) // { // pos = _pos; // dir = _dir; // } // }; int go(int s, int e) {
int dist[maxn][2]; for(int i=0; i<maxn; i++) { for(int j=0; j<=1; j++) { dist[i][j] = inf; } } deque<pair<int, int>> q; //pair>{node, edgedir} //making direction list here, q.push_back({s, 0}); //0>outgoing to node s dist[s][0] = 0; q.push_back({s, 1}); //1>incoming from node s dist[s][1] = 0; while(!q.empty()) { pair<int, int> cur = q.front(); //node int v = cur.first; int dir = cur.second; //dist int dv = dist[v][dir]; //guarenteed that shortest dist till cur node has been calc already q.pop_front(); //if(dv == inf) break;
if(cur.first == e) return dv; //gauarenteed via djikstra that this willbe minimest
//relax all the neighbours, and as you relax one , push into minheap the nodes for(auto it: adj[v]) { int to = it.fi; int dir2 = it.se; //previous //note that for type edge dir, you have relax for all neighbouring nodes int dist2=0; if(dir2 == dir) { dist2 = dist[v][dir2]; //dist[to][dir2] = min( dist[to][dir2], dist[v][dir2] ); } else dist2 = dist[v][dir] + 1; // dist[to][dir2] = min( dist[to][dir2], dist[v][dir] + 1);
//only relax and add to queue, if less than prev distance to this node if(dist2 < dist[to][dir2]) { if(dist2 <= dv) //less than equal to cur_dist q.push_front({to, dir2}); else q.push_back({to, dir2});
dist[to][dir2] = dist2;
}
} } return 1; } void solve() { cin>>n>>m; for(int i=1;i<=m;i++) { int x, y; cin>>x>>y; adj[x].pb({y, 0}); adj[y].pb({x, 1}); } int s, e; cin>>s>>e; //cout<<"hi"; int ans = go(s, e); cout<<ans<<endl; } signed main() { int t=1; //cin>>t; while(t) { solve(); } return 0; } I do not understand the final push back and front part. Why to push only if dist is less than dv? Why are we comparing it to dv? If it is for the right position in the queue of the pushed element(like in 01 bfs),then how do we know that the queue only has 01? That is the underlying part of the 01 bfs right?else it is dijkstra. I think the queue has difference of 1 between its min and max. Can you tell what all is true and exactly what is happening. I would really appreciate. Thank you Edited by author 04.05.2020 20:46 Edited by author 04.05.2020 20:47 Easy concept, just to think for a while. AC in one go! just use bfs as a modified version of dijkstra and you will be done 01 bfs on graph with 2 * n verticles. Used this idea, but instead I used another adj. list to store directions cin >> u >> v graph[u].push_back(v); direction[u].push_back(0); graph[v].push_back(u); direction[v].push_back(1); 0.046s AC Edited by author 12.07.2017 17:23 I am using dijkstra by adding a reverse edge of weight 1. Answer will be MIN ( Shortest distance, total_edges  shortest_distance); If you are using BFS, use a adjacency list. It's faster for finding the adjacents nodes. You too should use a "direccion list". It has the same size that the adjacency list, but it's filled with boolean values. For example, in the adjacency list of the node 1, you have nodes 2 3 4. If you need to go uphill from 1 to 2, in the correspondant place of the 2, you should write a 1, and if you need to go downhill, a 0. This is how I solved. I was stuck on time limit when I was using the same format of given data, but later I understood that the adjacency list it's very faster than 2 cols matrix (faster, but uses a lot more memory). Good luck, and try all the test posted in discussion. 3 3 1 2 2 3 3 1 1 3 how is this possible? from 1 to 2 there is an uphill road...from 2 to 3 there is also an uphill road...then how can there be a uphill road from 3 to 1??from 3 to 1 there should be a downhill road... correct me if i am wrong.. Don't worry about that, it's just an example and the contraints don't say nothing about. 6 6 4 2 1 2 4 5 2 3 2 6 6 4 1 5 answer : 0 Edited by author 07.01.2014 01:25 ? 6 6 4 2 1 2 4 5 2 3 2 6 6 4 1 5 answer : 0 Edited by author 07.01.2014 01:25 are you sure? isn't the answer is 2 the optimal route is: 1 > 2 > 6 > 4 > 5 and requires no gear changes Of course . it is right answer In this problem I use bfs and Dejikstra, in two cases I got AC, but my solutions are very slowly then others. I can't understand way ? How fast your Dijkstra's algorithm? The best program that I can write run in time 0.171s, but other users solv it in 0.031. My solution with Dijkstra work 0.312s :) 9 15 1 2 3 1 1 5 4 2 6 2 3 4 3 6 4 5 6 5 5 7 6 7 6 8 8 7 7 9 8 9 1 9 Ans: 0 BFS solution gets accepted.. but it fails in many cases. However the perfect solution to be used is Dijkstra's. The test cases do not contain cases where cycles terminate at nodes in between source and destination. Could you tell me some useful test, if you had the same problem?! Thanks ^_^ I use BFS, but WA12 :( Help me, pleas give me test 4 3 1 2 2 1 3 2 1 3 Nope, And I quote "There is at most one road between any two cities". 
