I applied Brute-Force approach in CLIQUED of April Challenge 2017. But, I am getting wrong answer in Test case 2 of subtask 1. Can anyone please point out the mistake in my brute-force method?
Thank you in advance.
Same thing happened to me…Atleast till I switched to python.
Your dijkstra implementation is faulty, why do use mark[x.second]? Target is to get minimum weight path, and we may not get mnimum weight in the first visit.
My code : I’ve used brute force Dijkstra : https://www.codechef.com/viewsolution/13234314
2 Likes
@neilit1992 is correct. First visit doesn’t guarantee minimal cost. There is no need to use that Boolean check there.
1 Like
In your code just set INF=10^17 you will get correct answer for subtask 1
This created a problem for me as well
1 Like
@neilit1992 Could you give me a test case where we do not get the shortest distance in first visit. Because as far as I know, when we pick the minimum weight vertex(lets say A) from min heap, then that particular weight is shortest distance to reach the vertex A (because if some other vertex, let’s say B contains a shorter path to reach A, then B should be extracted from min heap before A). Correct me if I am wrong here.
1 Like
@josh23 This is right but when you say this,it is for a particular path
Example We start from the source and encounter say vertex 1 first so we set its distance as min for now .Now when we explore the list of edges from 1, We set the minimum distances from a path to the edges attaching to 1 and path going through 1.This will keep on updating as soon as we keep on encountering some alternative paths(we can reach a vertex from different paths).Minheap will do this work for each edge and then when all are explored, all these local minimums on continuous updation give global minimum.
@josh123 The array contains min dist from source that is 1, initially 4 was updated to 60, but later it was updated to 15 which is the least weight, same is for undirected graphs, if you have further query, please let me know.
@josh23 please check my uploaded pic, with example, I think that will make it clear. @vidit_123 please let me it clear, we use relaxation in dijkstra’s algorithm (if(dist[u]+w1<dist[v])) only because, v can be reached from source through multiple nodes but we should consider the path that has least weight and the least weight path may or may not be reached in the first visit, one such example I’ve uploaded and there are many, check mit6006 lectures on dijkstra’s algorithm to get a strong grip on how dikstra’s work and what is relaxaztion algorithm.
@josh23 you are right.
@vidit_123 what is popped from the heap is guaranteed to be the minimum distance for that particular vertex as @josh23 says. The distance for that vertex is not modified again. Refer the Wiki page for more details.
1 Like
@neilit1992 the line in your code “if(dist[u]<d) continue;” achieves the same purpose as “if(mark[x.second]) continue;” in @hrushikesh_t’s code. The problem actually lay in the low value of INF. The implementation is not faulty.
@meoow yes thats true What I was explaining was that this happens continously alongwith relaxation i.e the same vertex may be explored by some other path and the distance may again be updated.
Oh okay, then it’s all good 
I guess the confusion arose due to the ambiguity of the term “visit”. By “visit” I think @josh23 meant popped from the heap, whereas you thought it meant distance relaxation.
This was the worst reason I got so many WA’s
Okay, yes it needed values larger than 10^9, i too used LLONGINT_MAX to get 1st sub task AC, didn’t see that he didn’t use large value as INF.
Thank you for rectifying @meooow
@meoow I’ve probably mistaken @josh123 question, but I learnt something new and that is once a node is popped from pq it’ll never get updated.
I just copied his solution updated INF and got AC . Damn this !! 
@neilit1992 yes that’s how it works, like a version of bfs for weighted edges. Once you pop a vertex from a bfs queue it doesn’t get updated again. Similar thing happens here 
Interestingly, the situation where a popped vertex may be required to get updated again is with negative weights, and that’s why Dijkstra’s algorithm is said to not work for negative weights.
1 Like
@neilit1992 I think we both interpreted the meaning of “visit” differently. For me, visit is when we extract the vertex from heap(assigning it the final weight) and for you it must be when we traverse it for the first time.
Now after reading the editorial, I tried to the solve the second subtask by using the method of introducing a fake vertex in the graph in the form of star topology.
But still I am getting TLE in second subtask. Can anyone point out the mistake in my code?
Here is the link to my code https://www.codechef.com/viewsolution/13372596