Packages Par Avion

You have been asked to help manage an airmail package delivery system for a company called Packages Par Avion (PPA). PPA works at a number of airports. At each airport they maintain a reception desk where customers can bring packages. They run a fleet of aircraft flying between the airports. PPA works with a ground transport company called PPT that takes responsibility for delivery of packages to their final destinations. Your task is to write software to determine how packages should be loaded onto planes.

Operations at each airport are as independent of those at other airports as possible. The day to day operation of a PPA branch is very structured. From 9 am to 5 pm each day parcels are accepted at reception. When a customer brings a parcel to reception, it is first weighed. The weight is rounded up to the nearest multiple of 1kg. The customer provides the delivery address and the value of the parcel in dollars. Staff determine the closest airport to the delivery address and record that, along with a time stamp, on the parcel. The time stamp is a real number – recorded in days and fractions of a day. The low precision bits of the time stamp are coded to ensure globally unique times across the company’s operation – no two parcels get the same time stamp. The reception area has limited capacity for storing parcels. If accepting a parcel would cause that capacity (sum of rounded parcel weights) to be exceeded, the parcel will be rejected.

At 5.05 pm each day, parcels are moved from reception and added to any already at the loading bay (those waiting from previous days, or parcels at an intermediate point in a multi-stage journey). Next, each branch sends an email message to every other branch stating the total weight (sum of rounded weights) of parcels they have in their loading bays. Planes are then loaded with parcels and fly to their destinations, always arriving in good time to complete unloading before the next day’s work begins. After unloading: if parcels are at their final destination, they are passed on to PPT, and can be assumed to be delivered. Otherwise they are held in the loading bay, ready for the next stage of their journey. Note: All airports operate in the same time zone.

Your software must assign parcels to planes. PPA policy is to do this as follows. Firstly a next hop is chosen for each parcel. The hop chosen is the first stop on the route which is a shortest sequence of plane trips – ie: a shortest number of hops. Where there is more than one route of shortest length, choose the one whose first step is to the airport with the lowest weight of parcels currently at their loading bay. If this is still ambiguous chose the first step airport with the lowest airport number. If there is no route to the parcel’s destination, it is left in the loading bay. Secondly, load as many parcels as possible on to the planes chosen for the first steps in their routes. Parcels are chosen firstly to maximize the value of cargo on board the plane, and secondly to give priority to the oldest parcels. Of two sets of parcels with equal total value and timestamps {1.4, 1.6, 1.7} and {1.4, 1.5, 1.9} the latter would be chosen. If parcels don’t fit on their assigned plane, they are left in the loading bay for the next day.

The input consists of a number of loading problems. The first line of each problem has five integers (A, F, P, B and C) separated by single spaces (all input takes this form – numbers separated by single spaces, no leading or trailing spaces). A is the number of other airports (numbered 1 to A, excluding the one you are working at); F is the number of flights for the day; P is the number of parcels that customers bought in during the day; B is the number of parcels already in the loading bay at the start of the day; and C is the capacity of the reception area. The next A lines give the total weight of parcels at each airport’s loading bay. Then F lines describe flights (hops). Each of the flight lines has three integers: the starting airport(s), the destination airport(d), and the capacity(c) of the plane in kg. Your airport is numbered 0 in the flight information. Following that are P lines describing parcels bought in by customers (remember, some may not be accepted). Each parcel line has a timestamp(float t), a rounded weight(integer w), a final destination airport(d) and a value(integer v). These lines are in order of timestamp. Last, there are B lines for the parcels waiting in the loading bay. They take the same form as the P lines. These are also in timestamp order. End of input is indicated by an initial problem line with 5 zeroes. Note that there is at most one flight between any two airports on one day. Limits are as follows: 1 <= A <= 30; 1 <= F <= 100; 0 <= P+B <= 5000; 1 <= C <= 150

For each flight leaving from your airport (airport 0), show the total value of parcels loaded. Write one line per flight, with the flight number (0, 1 …) and the total value of parcel loaded. Flights are numbered from 0 in the order input. Lines should be written flight number order.