## 11635 - Hotel booking

Moderator: Board moderators

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

### Re: 11635 - Hotel booking

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

catweazle352
New poster
Posts: 10
Joined: Wed Aug 14, 2013 7:53 pm

### Re: 11635 - Hotel booking

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
It's easy to beef about something - but it's much harder to make it better

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

### Re: 11635 - Hotel booking

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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11635 - Hotel booking

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
Check input and AC output for thousands of problems on uDebug!

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

### Re: 11635 - Hotel booking

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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11635 - Hotel booking

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.
Check input and AC output for thousands of problems on uDebug!

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

### Re: 11635 - Hotel booking

Random input, what a nifty feature!

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

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 11635 - Hotel booking

Code: Select all

Get AC
Last edited by Repon kumar Roy on Thu Oct 30, 2014 12:03 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11635 - Hotel booking

Try the random input at http://www.udebug.com/UVa/11635
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 11635 - Hotel booking

This input saved my day

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