Search code examples
graphdynamic-programmingbellman-ford

Calculate the number of trips in graph traversal

Hello Stack Overflow Community,

I'm attempting to solve this problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1040

The problem is to find the best path based on capacity between edges. I get that this can be solved using Dynamic Programming, I'm confused by the example they provide:

Map

According to the problem description, if someone is trying to get 99 people from city 1 to 7, the route should be 1-2-4-7 which I get since the weight of each edge represents the maximum amount of passengers that can go at once. What I don't get is that the description says that it takes at least 5 trips. Where does the 5 come from? 1-2-4-7 is 3 hops, If I take this trip I calculate 4 trips, since 25 is the most limited hop in the route, I would say you need 99/25 or at least 4 trips. Is this a typo, or am I missing something?

Solution

  • Given the first line of the problem statement:

    Mr. G. works as a tourist guide.

    It is likely that Mr. G must always be present on the bus, thus the equation for the number of trips is:

    x = (ceil(x) + number_of_passengers) / best_route

    rather than simply:

    x = number_of_passengers / best_route

    or, for your numbers:

    x = (ceil(x) + 99) / 25

    Which can be solved with:

    x == 4.16 (trips)