All submissions for this problem are available.
XYZ is an International Airline Company. It has flights between different cities across the globe but does not have a direct flight for all the pairs of cities. Flights are such that, all the cities with an airport are reachable by other city either by a direct flight or through other cities. Total number of flights is of the order of number of airports.
For the past few years, their statistics are given below:
- 2005 - 487 flights covering 319 different airports.
- 2007 - 782 flights covering 549 different airports.
- 2009 - 1197 flights covering 886 different airports.
They are planning to start a new flight between cities x and y, whose cost would be C units for the passengers. They need to calculate the percentage decrease in the total minimum cost for all pair of cities. So, let say total minimum cost to travel between all pairs of cities is initially C1 and after the new flight introduction becomes C2. You need to calculate (C1-C2)X100/C1.
First line would give t (number of test cases).
Each test case starts with line containing n(number of cities) and f(number of flights) seperated by space.
All the cities are numbered as 0,1,2,...,n-1.
Next f lines will give, index of two cities(i and j) and the cost of flight(C).
Each case ends with a line containing x and y with its cost separated by space.
C<=30000 units (is always an integer)
For each test case output the percentage decrease rounded off to two decimal places on a separate line.
Input: 2 3 2 0 1 3500 1 2 4000 0 2 2700 5 7 0 1 5500 2 3 8100 4 0 4300 1 2 2300 0 3 6000 4 2 3100 3 4 3700 1 3 2800 Output: 32.00 14.93
|Time Limit:||0.728261 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.