SP11873 FUKU11J - Round Trip

[English](/problems/FUKU11J/en/) [Vietnamese](/problems/FUKU11J/vn/)Jim is planning to visit one of his best friends in a town in the mountain area. First, he leaves his hometown and goes to the destination town. This is called the go phase. Then, he comes back to his hometown. This is called the return phase. You are expected to write a program to find the minimum total cost of this trip, which is the sum of the costs of the go phase and the return phase. There is a network of towns including these two towns. Every road in this network is one-way, i.e., can only be used towards the specified direction. Each road requires a certain cost to travel. In addition to the cost of roads, it is necessary to pay a specified fee to go through each town on the way. However, since this is the visa fee for the town, it is not necessary to pay the fee on the second or later visit to the same town. The altitude (height) of each town is given. On the go phase, the use of descending roads is inhibited. That is, when going from town _a_ to _b_, the altitude of _a_should not be greater than that of _b_. On the return phase, the use of ascending roads is inhibited in a similar manner. If the altitudes of _a_ and _b_ are equal, the road from _a_ to _b_ can be used on both phases.

N/A

N/A