10702 - Travelling Salesman

zhou junyu · Post by **zhou junyu** » Mon Aug 30, 2004 4:40 pm

I use DP to solve this problem. The complexity of my algo is lg(T)*C^3

my program take about 2 second to run all the test case.

How to make the time less than 1 second?
any better algo?

Observer · Post by **Observer** » Mon Aug 30, 2004 5:01 pm

My Pascal solution, having complexity of T*C^2, runs in 0.6 sec.

zhou junyu · Post by **zhou junyu** » Mon Aug 30, 2004 5:44 pm

yup, I got it, thanks.

Observer wrote:My Pascal solution, having complexity of T*C^2, runs in 0.6 sec.

anupam · Post by **anupam** » Wed Sep 15, 2004 9:37 pm

Would you please describe your procedure plz (just the algorithm)? Seeming my algo. is totally wrong.

Observer · Post by **Observer** » Thu Sep 16, 2004 5:52 am

A "state" can be given by : [current location, number of inter-city travels he has done].

Try to think of a way to fill the table.

uzurpatorul · Post by **uzurpatorul** » Fri Oct 22, 2004 8:01 pm

use dynamic programming and store the max value per step, the algo to find the max is:

int findMax(int c, int s, int e, int t, int step) {

if (step == t) {
for (i = 0; i < e; i++)
Max(cost[s][endcity - 1])

}
else
for (j = 0; j < c; j++) {
Max(cost[s][j]+ findMax(c, j, e, t, step + 1));

}
return max;
}

Nazmul Quader Zinnuree · Mon Apr 03, 2006 5:42 pm

Hello,
I've found no posts on this problem. Is it so easy or soo hard one?
Plz, somebody give me some hints on how to solve this problem. How to form the DP table? In details.....

Thanks?

Zuza · Post by **Zuza** » Thu Apr 26, 2007 12:43 pm

I'm printing the output with

Code: Select all

printf( "%d\n", best );

just as the problem suggests it and I don't know how to get rid of the presentation error.
I tried leaving blank after each set and leaving a blank line between each set.

sohel · Post by **sohel** » Thu Apr 26, 2007 6:23 pm

For each input set produce one line of output, the total profit he can earn in the corresponding tour.

Why are you concerned about printing additional blank lines?
There shouldn't be any blank lines at all.

.. and don't create a new thread for a problem that already exists.

Zuza · Post by **Zuza** » Thu Apr 26, 2007 7:25 pm

My original method ( printf( "%d\n", best ); ) prints a line per set.

sohel · Post by **sohel** » Thu Apr 26, 2007 7:37 pm

Can you PM me your code?

Ron · Post by **Ron** » Tue Feb 19, 2008 11:08 am

i am getting TLE in DP solution and getting WA in brute force solution....plz tell me problems ....

EDIT : ACed by T * C^2 complexity

golden eye · Post by **golden eye** » Wed Jan 26, 2011 10:02 am

how the output is 7 for the sample test case ??

Shafaet_du · Post by **Shafaet_du** » Wed Jun 08, 2011 9:44 am

1-3,3-2
5+2=7

@li_kuet · Post by **@li_kuet** » Mon Jun 18, 2012 12:34 am

Why i am getting Wrong Answer ????
here is my code >>

Code: Select all

Removed After AC :)
Silly mistake at the time of function calling .............

OJ Board