Description
There are C cities connected by M flights. Each flight starts from city U and arrives at V with a price P. Several airliners provide the service for the cities, and there may be multiple flights operated by different airliners between the same pair of cities.
Now given all the cities and flights, together with the starting city SRC and the destination DST, your task is to find the lowest cost from SRC to DST with up to cost W. If there is no such a route, output -1.
Note that you need to pay 5 additional units of cost for each change of airlines at one city.
Example.
There are three cities and two airlines. The airline 0 has two routes. The first route is from city 0 to city 1, and its cost is 1. The second route is from city 1 to city 2, and the cost is 10. On the other hand, the airline 1 only flies from city 1 to city 2, and its cost is 2.
If you want to fly from city 0 to city 2 with the minimum cost, you will take airline 0 from city 0 to city 1 (incurring 1 unit of cost), and then take airline 1 from city 1 to city 2 (spending 2 units of cost). However, as a change of airlines occurs at city 1, you have to spend 5 additional units of cost. Therefore, the minimum cost you spend from city 0 to city 2 is 1 + 2 + 5 = 8, as illustrated in the following figure.
However, if airline1 cancels the route from city 1 to city 2, and you still want to travel from city 0 to city 2. In this case, the minimum cost that you have to pay is 1 + 10 = 11, since you take the same airline.
You should implement:
- Add U V P A: Add a flight route, which goes from U to V with cost P operated by airline A.
Note that it is possible that multiple airlines fly from U to V, and their prices may not be the same. Moreover, the airline may update the cost of the route in the future inputs.
For example, “Add 0 1 4 0” indicates that a flight from city 0 to city 1 costs 4 for airline 0. After a few instructions, there is an instruction “Add 0 1 5 0”, and it means that airline 0 updates the cost. Therefore, the cost of airline 0 from city 0 to city 1 becomes 5 after this instruction.
2. Delete U V A: Delete all the flights from U to V operated by airline A.
For example, “Delete 1 2 0” indicates the flight from city 1 to city 2 operated by airline 0 is cancelled.
Note that if there is no flight from U to V operated by airline A, you don’t have to do anything.
3. Request SRC DST W: A person wishes to book the cheapest ticket from SRC to DST with the overall cost at most W. Print the lowest cost from SRC to DST with up to cost W. If there is no such a route, output -1.
For example, “Request 0 2 20” means a person wants to spend at most 20 units of cost to fly from city 0 to city 2. You should output the minimum cost to fly from city 0 to city 2 and the minimum cost cannot exceed 20. If it is impossible, output -1.
Here is one hint for you. Sometimes all the costs of the routes are the same. If this case occurs, a computationally efficient approach should be implemented.
Vector, Queue and String STL are allowed to use.
Input
The first line contains an integer C, which is the number of cities.
The second line contains an integer N, which is the number of instructions.
The following N lines are the instructions.
Constraints of parameters (All the parameters are integers):
C (number of cities): 0 < C <=210
N (number of instructions): 0 < N <= 100000
M (number of flights): 0 < M <= 19900
P (cost of a flight): 0 < P <= 1000
A (number of airlines): 0 < A <= 50
W (cost limit in a request): 0 < W <= 10000
The city’s index starts from 0.
Output
You only need to output the result when a “Request” appears in the input. For a “Request” instruction, print the minimum cost from SRC to DST with cost at most W. If there is no such a route, output -1. After each output, enter a new line.