CareerCup

Delhi Route Traffic Optimizer

Traffic congestion is an annoying issue in Delhi, the capital of India. Every morning thousands of people drivea residential area to the International Technology Park (ITPL). There are various routes one can take to reach ITPL and each route takes its own time making some routes faster than the others. People obviously take faster routes which causes congestion on those roads too. Congestion results into increased travel time, air pollution and wastage of fuel. As a Traffic commissioner of Delhi, you are asked to optimize the traffic by putting toll to various roads so that resultant cost of every route (driving time cost and toll cost) ends up the same. This has to be done in such a way that any driver pays toll only once no matter which route he/she takes.roads have one-way traffic and there is no cycle in any of the routes. You need to create a toll plan for a given road layout.

The toll plan must adhere to following rules:

1. Toll should be levied in such a way that perceived cost (base road cost and toll cost) remains same forroads.
2. The tolls should be levied such that the total cost for each route is minimized.
3. A route cannot have more than one toll.
4. In case of multiple solutions for a route, add toll to a road that is closer to destination.
In some use cases, it might be impossible to impose tolls that satisfy the above conditions.

http://qa.geeksforgeeks.org/11340/delhi-route-traffic-optimizer