Page 3 of 3

Re: 11635 - Hotel booking

Posted: Wed Oct 08, 2014 2:30 pm
by Target979
I always (in the code) visit a city if it can be reached in less time than any of the previous visits during the same day or if it hasn't been visited yet. This cover all cases I can think of. I get the correct output for all testcases in this thread but WA when I submit :cry:

Re: 11635 - Hotel booking

Posted: Wed Oct 08, 2014 3:11 pm
by catweazle352
I am not quite sure if I understand your bfs code correctly, so I'd like to apologize in advance for any misunderstanding. I think one must use a kind of priority queue of visits during the bfs in order to get the correct answer and I cannot quite find a prio queue in your code (Sorry again if I misunderstood your code).

My strategy was to store all "visits" (consisting of the city, the preceeding visit, the no of hotels slept in (including this visit) and the minutes since last sleeping visit) into a prio queue.

Then I did a bfs. During that bfs I created new "visits" into my prio queue. But I did *not* use *each* edge but checked each edge of the current node and checked each edge against those visits stored in the prio queue in order to avoid cycling infinite. The distance criteria I used was a pair consisting of (#1No Of Hotels, #2minutes since last stay).

That strategy worked for me.

Kind Regards

Christof

Re: 11635 - Hotel booking

Posted: Wed Oct 08, 2014 3:33 pm
by Target979
My approach is to perform a bfs-search from the first node and visit all nodes I can visit without violating the time constraint. All nodes encountered containing a hotel are added to a queue and if the final node is reached the algorithm terminates. Once no more nodes can be reached a new bfs-search is performed from every hotel node in the queue and adding all reachable hotels. This continue until there are no more hotels to visit or a solution is found.

I think it should be possible to solve it with this approach, but I will have a look at your suggestion and see what I can come up with.

Re: 11635 - Hotel booking

Posted: Wed Oct 08, 2014 9:21 pm
by brianfry713
Input:

Code: Select all

19
10 2 4 5 6 8 9 10 11 15 19
17
16 2 160
8 2 511
19 3 58
6 4 292
17 3 125
4 10 196
2 17 513
9 12 295
1 6 579
16 3 577
14 12 593
15 2 18
17 9 295
17 4 89
1 2 431
10 6 83
4 15 396
0
AC output:

Code: Select all

1

Re: 11635 - Hotel booking

Posted: Thu Oct 09, 2014 1:29 am
by Target979
Think there must be an error in your AC output (should be one). The following path can be taken with one hotel stay: 1 - 6 STAY 6 - 10 - 4 - 17 -3 - 19.

By the way thanks to all of you for taking some of your time to help me out. Really appreciated.

Re: 11635 - Hotel booking

Posted: Thu Oct 09, 2014 8:50 pm
by brianfry713
You are correct, I edited my previous post.

See:
http://www.udebug.com/UVa/11635
Click "Random Input", "Go!"
Your code fails on some of them.

I solved it by running Dijkstra's Algorithm once for each day until you reach city n or can't reach a hotel you haven't already stayed at. On day 0 you start from only city 1, on each following day you start from all hotels you could reach the previous day and hadn't already stayed at.

Re: 11635 - Hotel booking

Posted: Thu Oct 09, 2014 11:09 pm
by Target979
Random input, what a nifty feature!

Now I have something to work with, thanks a lot.

Re: 11635 - Hotel booking

Posted: Tue Oct 28, 2014 7:39 pm
by Repon kumar Roy

Code: Select all

Get AC

Re: 11635 - Hotel booking

Posted: Wed Oct 29, 2014 10:29 pm
by brianfry713
Try the random input at http://www.udebug.com/UVa/11635

Re: 11635 - Hotel booking

Posted: Wed Oct 29, 2014 11:37 pm
by Repon kumar Roy
This input saved my day :evil:

Code: Select all

9 
3 1 3 4 
14
8 5 18 
4 8 122 
6 5 234 
7 7 404 
8 7 188 
3 6 596 
8 7 12 
6 6 26 
3 4 69 
4 8 400
 8 1 325 
5 9 381 
7 3 580 
5 4 400 
AC output : 1

Please check ....