bfs is unnecessary, the dist between x1,y1 and x2,y2 is
max(x1~x2, y1~y2). use bitmask DP, that wont give tle, i used this with time complexity O(n^2*2^n) and memory O(n*2^n) as described earlier in this forum
10944  Nuts for nuts..
Moderator: Board moderators

 Experienced poster
 Posts: 120
 Joined: Sat Nov 01, 2003 6:16 am
 Location: Dhaka (EWU)
I have solved this problem by this way
but a single if condition has confused me...
This problem takes only 1.76 seconds
but when i have changed a if conditions format then it takes 6.52 seconds
why can any body explain me ...
it takes 6.52 seconds
it takes 1.76 seconds
Thanks
MAP
After discussion i will cut my code
but a single if condition has confused me...
Code: Select all
...................................
but when i have changed a if conditions format then it takes 6.52 seconds
why can any body explain me ...
Code: Select all
.................................
Code: Select all
if (u) {
if (Graph[x][u] < sum) return ;
else Graph[x][u] = sum;
}
Code: Select all
if (u) {
if (Graph[x][u] > sum) Graph[x][u] = sum;
else return ;
}
Thanks
MAP
After discussion i will cut my code
Last edited by mohiul alam prince on Sun Jan 28, 2007 9:38 am, edited 1 time in total.

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
mohiul alam prince wrote:it takes 6.52 secondsCode: Select all
if (u) { if (Graph[x][u] < sum) return ; else Graph[x][u] = sum; }
it takes 1.76 secondsCode: Select all
if (u) { if (Graph[x][u] > sum) Graph[x][u] = sum; else return ; }
Thanks
MAP
After discussion i will cut my code
Look at this part:
Code: Select all
if (u) {
if (Graph[x][u] > sum) Graph[x][u] = sum;
else return ;
}
Code: Select all
if (u) {
if (Graph[x][u] <= sum) return ;
else Graph[x][u] = sum;
}
Code: Select all
if (u) {
if (Graph[x][u] < sum) return ;
else Graph[x][u] = sum;
}

 Experienced poster
 Posts: 120
 Joined: Sat Nov 01, 2003 6:16 am
 Location: Dhaka (EWU)