decoder123's blog

Help in UVA-11635 Hotel Booking
By decoder123, history, 9 years ago, In English

I have tried these problem.(link). But I am stuck still now after getting the hint (Dijkstra+ BFS). Can anybody please provide me with an editorial(algorithm)? What do we need to do to solve this problem?

I mean it would be better "if some one provides me with the thinking process". Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Key observation is that h ≤ 100. You can look for f[i, j] (h2 cells) — shortest path between c[i] and c[j]. If it is less or equal to 10, it can be considered. If no, then you can't use this way. For answering the query you should start bfs and find fastest way to reach destination vertex.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    From your comment what I understand is f[i,j]=shortest path between city i and cityj. Now these cities may have hotels or may not.

    Now the 2-d array f[1..100][1..100] ..keeps tracks of whether there is a valid path from i to j with the condition f[i][j] <=10 hour.

    Now start a bfs from 1. Then we will get a path to reach j but How do we ensure that is the shortest? As BFS doesn't give shortest path in weighted graphs.

    Too many doubts I have in mind...

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Look.

      Lets reduce the graph to what we should look for. We are only interested in hotels and both start and destination points. Call them good. So for each good vertex we are to calculate shortest distances to other cities, even bad ones.

      Now lets forget about bad points, as soon as we now from fixed good point what good points are reachable within 10 hours. Finally there is a constrain for minimizing number of visited hotels. So in new graph which consist of good points and edge is between vertexes what can be reached from one to another within 10 hours you are to find shortest path between 2 points.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For the first phase we can apply APSP algo (like Floyd Warshall).

        Then we will recreate a graph with vertex 1 and vertex n and all the good points. They are connected with all possible paths (thinking that way). Fully connected graph with all the paths with <=10 hrs. Now in that graph we are damn sure that all the paths <=10 hr and they are shortest.

        We have only one thing to worry now..whether vertex-1 to vertex n is reachable or not. If reachable then we will just use BFS to get the answer as we don't need to consider edge weights here...we only worry about minimizing the number of hotels. If we consider each edge of weight 1 then that will suffice.

        I have understood this much .** If there is any flow please teach me/point me.**

        [Note: I have started realizing that why we can forget about bad points..Is it becuase their effect/contribution in shortest path is already considered in APSP algorithm? ]

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Right. But it is not fully connected. Not all pairs of good vertexes can be reached from one end to another within 10 hours. As soon as we consider only pairs of hotels end to end reachable in 10 hours we can forget about weights as you said. Then simple BFS. You aren't able to use APSP since its time complexety n3, you intially have 105 vertexes. You better to use Dijkstra algorithm (h times dijkstra).

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            oh! yes..here n=10^5..O(n^3) APSP not possible...thanks for your time and elaborate answer. I understood the whole thing.

            → Reply