Programming contests

ECN programozó csapatverseny, 2018. május 12.

May 12, 2018 10:15 AM – May 12, 2018 3:15 PM

Speed Pizza

A local pizza restaurant offers pizza delivery services to customers directly to their home. The restaurant receives orders and delivers the pizza using motor scooters. Orders are taken in the order of their arrival and assigned to a driver. Each driver will have his own scooter and can only pick up a single pizza order for delivery to a location. After each delivery, a driver returns to the restaurant to pick up the next order, if any available, until all orders are delivered. The location of an order can be any location on the map, but will never be the location of the restaurant. Locations are linked by two-way roads which have an associated cost, the time needed for a motor scooter to go from a location to another.

The manager of the restaurant wants to deliver the orders received using the available scooters as soon as possible in order to keep the customers happy. You are given:

  • a map of locations numbered from 1 to l, linked by two-way roads with a time cost;
  • the location of the restaurant;
  • the total number of available scooters;
  • the orders the restaurant receives.

Your task is to find the minimum cost to deliver all orders to their location. The orders must be taken in the order they arrive.

Input Specification

The first line of the input consists of a pair of numbers l and r, representing the number of locations (numbered from 1 to l) and the number of roads which link them. On the next r lines, the two-way roads are listed, given in the form of location l1, location l2, and cost c, meaning that from location l1 to location l2 (and vice versa) the time to arrive is c.

On the next line, the location p of the restaurant is given.

After the restaurant location, two numbers representing the number of scooters s and the number of orders o are provided on a new line. The final line contains the locations for the o orders received by the restaurant, separated by a space.

Input Limits and Constraints

  • 1 < l < 100 000;
  • 1 < s < o;
  • the order locations will always be accessible from the restaurant;
  • the time cost of delivering an order will never be higher than 1 000 000 000;
  • there is no limitation on the number of scooters on a road at a moment in time;
  • all the orders are considered delivered when all the scooters have returned to the restaurant, and no order is to be taken.

Output Specification

The output should contain a single line representing the minimum cost to deliver all the orders to their destination locations.

Sample Input

  1. 5 6
  2. 1 2 1
  3. 1 4 2
  4. 4 3 4
  5. 2 3 2
  6. 4 5 3
  7. 3 5 6
  8. 1
  9. 2 4
  10. 3 5 4 2
download as text file

Output for Sample Input

  1. 12
download as text file

Explanation

Restaurant: 1

Number of scooters: 2

Order locations: 3 5 4 2

The computation for the minimum-cost route and the order-scooter allocations are displayed in the table below:

Order location Minimum route to location Minimum cost (roundtrip) Scooter 1 Scooter 2
3 1 → 2 → 3 6 x
5 1 → 4 → 5 10 x
4 1 → 4 4 x
2 1 → 2 2 x
Total time 10 12

The order timeline is shown below:

Note: In the example above, the final order (2) could have been taken by any of the two scooters, as at time 10 they were both at the restaurant.

University of Debrecen; Faculty of Informatics; v. 03/01/2019