Page **3** of **3**

Posted: **Fri Jun 23, 2006 2:33 pm**

by **ayon**

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

Posted: **Tue Aug 29, 2006 11:14 pm**

by **sclo**

The dp for TSP is one of the standard dp for subsets. It is good to learn it.

It is basically 3 nested for loops. At the end, we need to take care of the last segment back to the start vertex.

Posted: **Wed Jan 17, 2007 10:57 pm**

by **mohiul alam prince**

I have solved this problem by this way

but a single if condition has confused me...

Code: Select all

```
...................................
```

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 ...

Code: Select all

```
if (u) {
if (Graph[x][u] < sum) return ;
else Graph[x][u] = sum;
}
```

it takes 6.52 seconds

Code: Select all

```
if (u) {
if (Graph[x][u] > sum) Graph[x][u] = sum;
else return ;
}
```

it takes 1.76 seconds

Thanks

MAP

After discussion i will cut my code

Posted: **Thu Jan 18, 2007 7:33 am**

by **emotional blind**

mohiul alam prince wrote:
Code: Select all

```
if (u) {
if (Graph[x][u] < sum) return ;
else Graph[x][u] = sum;
}
```

it takes 6.52 seconds

Code: Select all

```
if (u) {
if (Graph[x][u] > sum) Graph[x][u] = sum;
else return ;
}
```

it takes 1.76 seconds

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 ;
}
```

which is equivalent to:

Code: Select all

```
if (u) {
if (Graph[x][u] <= sum) return ;
else Graph[x][u] = sum;
}
```

but your equivalent code was

Code: Select all

```
if (u) {
if (Graph[x][u] < sum) return ;
else Graph[x][u] = sum;
}
```

the function returns when Graph[x]

<sum, but in first case function returns when Graph[x]<=sum.. so your code dont return when Graph[x]==sum. thats why it takes more time.

Posted: **Sun Jan 28, 2007 9:40 am**

by **mohiul alam prince**

Thankx EmotionalBlind

i have got it..

MAP

### Thanks

Posted: **Fri Apr 06, 2007 4:03 pm**

by **nymo**

I 've got ACC with topdown approach (recursion with memoization) ... at last.

Thanks everyone. I 've done pretty much what ayon said.