CF1307G Cow and Exercise

Farmer John is obsessed with making Bessie exercise more! Bessie is out grazing on the farm, which consists of $ n $ fields connected by $ m $ directed roads. Each road takes some time $ w_i $ to cross. She is currently at field $ 1 $ and will return to her home at field $ n $ at the end of the day. Farmer John has plans to increase the time it takes to cross certain roads. He can increase the time it takes to cross each road by a nonnegative amount, but the total increase cannot exceed $ x_i $ for the $ i $ -th plan. Determine the maximum he can make the shortest path from $ 1 $ to $ n $ for each of the $ q $ independent plans.

N/A

N/A