## 10702 - Travelling Salesman

Moderator: Board moderators

zhou junyu
New poster
Posts: 2
Joined: Mon Sep 15, 2003 5:58 pm

### 10702 - Travelling Salesman

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
My Pascal solution, having complexity of T*C^2, runs in 0.6 sec.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

zhou junyu
New poster
Posts: 2
Joined: Mon Sep 15, 2003 5:58 pm
yup, I got it, thanks.

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Would you please describe your procedure plz (just the algorithm)? Seeming my algo. is totally wrong.
"Everything should be made simple, but not always simpler"

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

uzurpatorul
New poster
Posts: 5
Joined: Fri Oct 22, 2004 10:21 am
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;
}

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:

### 10702 - Travelling Salesman

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
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

### 10702 PE

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
For each input set produce one line of output, the total profit he can earn in the corresponding tour.
There shouldn't be any blank lines at all.

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

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
My original method ( printf( "%d\n", best ); ) prints a line per set.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Can you PM me your code?

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### whatz wrong .......... ???????????????????????????

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
Last edited by Ron on Sun Oct 25, 2009 8:59 am, edited 1 time in total.

golden eye
New poster
Posts: 2
Joined: Sat Jan 03, 2009 9:24 am

### Re: 10702 - Travelling Salesman

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

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10702 - Travelling Salesman

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

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
``````Removed After AC :)