Page 1 of 2
10702 - Travelling Salesman
Posted: Mon Aug 30, 2004 4:40 pm
by zhou junyu
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?
Posted: Mon Aug 30, 2004 5:01 pm
by Observer
My Pascal solution, having complexity of T*C^2, runs in 0.6 sec.
Posted: Mon Aug 30, 2004 5:44 pm
by zhou junyu
yup, I got it, thanks.
Observer wrote:My Pascal solution, having complexity of T*C^2, runs in 0.6 sec.
Posted: Wed Sep 15, 2004 9:37 pm
by anupam
Would you please describe your procedure plz (just the algorithm)? Seeming my algo. is totally wrong.
Posted: Thu Sep 16, 2004 5:52 am
by Observer
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.
Posted: Fri Oct 22, 2004 8:01 pm
by uzurpatorul
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;
}
10702 - Travelling Salesman
Posted: Mon Apr 03, 2006 5:42 pm
by Nazmul Quader Zinnuree
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?
10702 PE
Posted: Thu Apr 26, 2007 12:43 pm
by Zuza
I'm printing the output with
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.
Posted: Thu Apr 26, 2007 6:23 pm
by sohel
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.
Posted: Thu Apr 26, 2007 7:25 pm
by Zuza
My original method ( printf( "%d\n", best ); ) prints a line per set.
Posted: Thu Apr 26, 2007 7:37 pm
by sohel
Can you PM me your code?
whatz wrong .......... ???????????????????????????
Posted: Tue Feb 19, 2008 11:08 am
by Ron
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
Re: 10702 - Travelling Salesman
Posted: Wed Jan 26, 2011 10:02 am
by golden eye
how the output is 7 for the sample test case ??
Re: 10702 - Travelling Salesman
Posted: Wed Jun 08, 2011 9:44 am
by Shafaet_du
1-3,3-2
5+2=7
Re: 10702 - Travelling Salesman
Posted: Mon Jun 18, 2012 12:34 am
by @li_kuet
Why i am getting Wrong Answer ????
here is my code >>
Code: Select all
Removed After AC :)
Silly mistake at the time of function calling .............