The plan is to revamp a road network for a city. The programme should assist the developer so that the cost to build it is of minimum cost. The key points are:
1. The city already has an existing road network, but the roads are narrow, old with full of potholes, making them virtually unusable. If a particular road segment is chosen by the programme, then that entire road segment needs to be rebuilt to meet the current needs.
2. There are some key locations in the city, which have become very important in the recent years and thus communication between these points should be very smooth and efficient. So, even if two such points are somehow connected (directly or indirectly) by revamped road(s), if the cost becomes higher than a specified limit, then the developer has to build/revamp a road segment (directly or indirectly) which makes the cost lower than the specified limit.
Your programme should accept a graph in the form of a cost matrix, and your programme should generate which roads are revamped and the corresponding cost involved.
The program should be in simple c++ language , easily understandable by the user.