Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- There is a directed graph with edge weights, each node represents a city, each edge represents an airplane traveling between two cities and the weight represents how many passengers can fly in that airplane.
- All seats of all the airplanes have been reserved in advance, so there’s no need to buy independent tickets for passengers. It’s not possible to use the same airplane twice. The flight i has a capacity of Hi passengers.
- There are Gi people in the city i. All the people have to reach city 1 by traveling on several flights. You can schedule the order of the flights as you wish.
- Also, there’s a probability that the flight i is cancelled, this probability is Pi. It’s impossible that two or more flights are cancelled.
- The cities are numbered from 1 to C.
- The flights are numbered from 1 to F.
- You have to answer the probability that all people reach the city 1.
- Constraints:
- 1 <= C <= 1000
- 1 <= F <= 10000
- 0 <= Pi <=1.0
- 0 <= Gi <= 1000
- 0 <= Hi <= 100
- The sum of all Pi is 1.0
- The graph contains no cycles
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement