13800 - TSP Logistics   

Status  |  Limits Submit

Description

Dorami established a logistics company, TSP (TransportS Perfectly) Logistics! To reduce the cost of transporting goods to the stores, we have to design a delivery route for the truck to minimize the travel length.

 

In this problem, please notice the following description:

  • All the goods are deposited at the cargo center (place 0). 
  • The capacity of the truck is 30 units, and each store has specific units of goods that are demanded to deliver.
  • We have to load the goods at the cargo center by not exceeding the maximum capacity of 30 units, deliver them and satisfy the demand for each store. 
  • You can't divide the goods that are going to deliver to the same store, that is, you have to deliver all the goods that a store are demanded at one time.
  • You might need to return to the cargo center several times since the capacity of the truck is limited. 
  • The truck starts from the cargo center, and after the delivery process, the truck should return to the cargo center. 
  • There are some roads between two places, You can travel from one place to another if there is a road between them.
  • Find the minimum length of the delivery route.

 

This is a partial judge problem. You can refer to 12498 - Partial Judge Example to know how a partial judge problem works.

In this problem, several structures are defined:

struct road {
    int length;               // The length of the road
    place *place;          // Point to the end of the road
};
struct place { 
    int id;                      // Index of place, 0 represents the cargo center, and 1~n represents the stores
    int demand;            // Each store has specific units of goods that are demanded to deliver.
    int numOfRoads;    // The number of roads that connect with this place
    road roads[P_NUM];
};

 

​You need to implement the function below to find the answer:

long long minRoute(place *p, int n);

 

For the sample input, one of the best strategies is: 

0 (Load 30) -> 1 -> 3 (Deliver 30) -> 1 -> 0 (Load 30) -> 1 (Deliver 14) -> 2 (Deliver 16) -> 0. The length of the delivery route is 24.

 

******Hint. 

  • [hint.pdf]    This is one of the concepts for solving this problem.​ You can refer to this and try to implement, or try to find your approach! 
  • ​In 13800.h, there is a function called"distance", which uses the technique of the Floyd–Warshall algorithm to find the shortest path between every two places. Uncomment and trace the code to understand the algorithm!
  • Dorami Thanks for your help!

Input

  • The first line contains two integers N and M - the numbers of stores and roads.
  • The second line contains N integers u1~uN - units of goods that are demanded to deliver for stores 1, 2, ..., N
  • The next M lines describe the roads, each of them containing 3 integers a, b, w - the indexes of the two places at the ends of the road and the length of the road.

It guarantees that you can travel from the cargo center to all the stores.

 

Test case constraints

  • 1 <= N <= 12
  • 1 <= M <= N(N+1)/2
  • 1 <= ui <= 30
  • 0 <= a, b <= N
  • 1 <= w <= 109
  • The capacity of the truck = 30

 

Output

Output one line contains the minimum length of the delivery route.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

13800.c

Partial Judge Header

13800.h

Tags




Discuss