Travel PlanProblem code: CF03 |
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.
Input
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.
t<=10
n<=1000, f<=2000
C<=30000 units (is always an integer)
Output
For each test case output the percentage decrease rounded off to two decimal places on a separate line.
Example
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
| Date: | 2010-03-26 |
| Time limit: | 3.5s |
| Source limit: | 50000 |
| Languages: | C C++ 4.0.0-8 C++ 4.3.2 |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
is it to be assumed that x
is it to be assumed that x and y will lie from 0 to n-1 only?
@TheCodebreakers: Yes, x and
@TheCodebreakers: Yes, x and y will lie between 0 and n-1.
Is n = 1, f = 0 0 0 123 x =
Is n = 1, f = 0
0 0 123
x = 0, y = 0, C = 45
valid case?
Sorry f = 1 for previous
Sorry f = 1 for previous query.
Invalid case. x and y can
Invalid case. x and y can never be same and so is i and j.
Also you can safely assume that f>0 and n>=2.
Is it possible that a flight
Is it possible that a flight already exists between x and y? Also, are the flights two way or one way?
@Codebreakers: No, it is not
@Codebreakers: No, it is not possible that a flight already exists between x and y. All flights are two ways. The cost is same back and forth for a set of cities.
Current ranking is available
Current ranking is available at http://www.codechef.com/teams/list/MANTH10/
1. Are all the costs
1. Are all the costs nonnegative?
2. Answer is rounded using mathematical rules, isn't it? I.e., 10.234 = 10.23 and 10.235 = 10.24, right? And are there some tricky cases where answer is very close to rounding edge?
@dzhulgakov: 1. No. Costs
@dzhulgakov:
1. No. Costs are always positive.
2. Yes. You can use printf("%.2lfn",ans) for rounding off.
It said that "The contest
It said that "The contest will last 6 hours and will have 8-10 problems." on the codefest website:
http://itbhu.ac.in/codefest/event.php?eid=5
Why there are only 4 problems?
@All: The judge test cases
@All: The judge test cases have been modified. The rejudge is in process, but still do submit your codes again. Penalities, if any applied currrenlty for correct submissions will be removed
@ForEver - We thought it
@ForEver - We thought it would be difficult to solve all the problems in the given time constraints, so reduced the number of problems
But as you see many people
But as you see many people have solved three problems.
So it is only one left on three hours.
Yes, and I'm a high-school
Yes, and I'm a high-school student so I didn't learn Matrix.
I can't understand the only left problem. (>_<|||)
If there are some other problem , I will try some else.
@Anton_Lunyov & ForEver: We
@Anton_Lunyov & ForEver: We can not add any more problems now. There are lots of other teams still trying the problems.
When my successful solution
When my successful solution will appear in the scoreboard? It is listed in My Submissions and All Submissions as Accepted but in scoreboard I still have only 2 problems
My submissions shows the
My submissions shows the problem as accepted, although the scoreboard is not updated. Can you update the scoreboard?
The ScoreBoard will be
The ScoreBoard will be updated tomorrow. The inconsistency is due to rejudging.
Final rankings will be considered after the error has been rectified.