11635 - Hotel booking

[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

[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

[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.

[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

[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.

[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.

[Target979]

Random input, what a nifty feature!

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

[Repon kumar Roy]

Code: Select all

Get AC

[brianfry713]

Try the random input at http://www.udebug.com/UVa/11635

[Repon kumar Roy]

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

Please check ....