SP2131 GETBACK - Get Back!

Somewhere deep in a desert lives a small, completely forgotten tribe N'Gubara. All the men, women and children of the tribe live with a few camels in the N'Gubara oasis (the N'Gubara people don't have great creativity when it comes to geography names). These poor people have only the N'Gubara well, a few acres of irrigated land and the N'Gubara cave. Yes, the cave. You do not remember exactly how you have come to N'Gubara. Maybe your car broke when you travelled across the desert. Maybe you jumped out of an airplane. Maybe you were brought here by Martians. But this does not matter now. You know that you are here, pretty far from any civilization. And you desperately want to go home. The only possibility how to get home is to walk across the desert to Desertville, the closest city. You have to use paths in the desert shown in your map. Each such path connects two restpoints. The N'Gubara oasis and Desertville are also considered to be restpoints. You can walk, but you need water. For each mile travelled, you have to drink one unit of water. You are able to carry at most C units of water at once. Thus, you can never walk more than C miles without replenishing your water supply. The shortest way to Desertville is probably much longer than C miles. It would thus seem that you will stay in N'Gubara forever, but there's a trick: at the end of each path, there is a restpoint with an empty water reservoir. You can transport water into a reservoir from N'Gubara or from other reservoirs where you stored some water previously. You can then use the stored water later on (the water doesn't evaporate). Of course, you can take only as much water from any reservoir as you brought into it. You may use as much water from the N'Gubara oasis as you need, but since water is very valuable in the desert, you promised that you will use only the minimal amount needed for your return to Desertville. In this task, we want you to compute the minimal amount of water you need.

N/A

N/A