i have used warshalls algorithm to find the shortest path but my solution gave a wa
i took a 2d matrix and initially i stored INF in matrix then
matrix[x][y]=0; and matrix[y][x]=1;
then i applied kruskals algo
which gave coreect answers for the given test case but wa when i submitted my solution .
A simple question how you get the thought for this like adding a reverse edge with weight 1 this makes the problem very easy. Is this a classical problem or i can use any other apporoach to solve this…please help.
Can any one give me test cases for which my code is giving WA…
Thnx for ur help…
Why is your modifies bfs working faster than Djiktra algorithm?
Here are my two solution using bfs(CodeChef: Practical coding for everyone) and using Djiktsta (CodeChef: Practical coding for everyone)
I tried implementing the method suggested by @asheshvidyut in Python. The result is here : CodeChef: Practical coding for everyone.
However, I exceed the time limit. I also rewrote the code with a merge to make it faster (but less readable), but I still get a TLE : CodeChef: Practical coding for everyone.
Am I doing something wrong or is Python inherently too slow ?
can some one please check this
http://www.codechef.com/viewsolution/4832243
and tell me where i did the mistake
I tried to submit this in D, and got a SISEGV!. Here’s the link to my submission: CodeChef: Practical coding for everyone
Then I just translated the same code to C++, and it was accepted!!!:
Here’s the link: CodeChef: Practical coding for everyone
The D version executed fine on my system (gdc 5.1). Can anyone please explain???
I have use dijkstra but getting tle can anybody help me in finding the reason
https://www.codechef.com/viewsolution/11997317
I have use dijkstra but getting tle can anybody help me in finding the reason
https://www.codechef.com/viewsolution/11997317
Hi @ambarpal I have done it by BFS using a queue. Here is my solution for reference : CodeChef: Practical coding for everyone . In the solution graph vector is the input graph and ans[i] stores the length of the shortest path from N to that node so far. It is updated if we find a shorter path. ans[1] will finally store the shortest length from n to 1.
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.
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?