Guesstimate Loss :
Difficulty Level : Hard
Submissions : 683
Asked In :
Marks :50
: 1 | : 6
An Online Taxi service is facing losses due to recent changes in its discount prices. To overcome the losses, the team has made a list of N places of a city with M routes. Each route has 3 components.
The first component is the pick-up position id, the second is the destination position id and the third is the cost per trip between the pickup and destination. If cost is +ve, company is making a profit else loss from that trip. If the pick-up and destination point are same, then that trip is known as a round trip.
Write an algorithm for the company's system that will calculate the maximum amount of money that they are losing in a round trip.
In case there is no round trip having -ve cost 0 loss is always the option.
First line contains two space separated integers number of cities N and number of routes M. $$$(1\le N,M \le 10000)$$$.
Next M lines contains 3 space separated integers U,V and W (Pick-up Position , destination and cost respectively) $$$(0 \le U,V \lt N)$$$ and $$$(-1000 \le W \le 1000)$$$.
Print a singe integer denoting the minimum amount of money that they are losing in a round trip.
4 5 0 1 -1 1 2 -2 2 0 -5 0 3 6 3 0 -19
-13
4 5 0 1 -1 1 2 -2 2 0 -5 0 3 6 3 2 3
-8
