Logistics
(Main file name: logistics)

John is a truck driver. He needs to deliver a truckload of packages to different destination cities. In each city other truck drivers can help transport part of the packages with their trucks. So nobody is required to solve the traveling salesman problem. Also, no driver is required to return to his starting city. Nevertheless, John has to pay for the distances the trucks travel, and he wants to find routes for himself and the helpers such that the total travel distance is minimized.

The problem can be formulated as a graph problem as follows: Given an undirected weighted graph, a starting vertex, and a set of destination vertices, find a subgraph of the graph that has the minimum cost and covers the starting vertex and all of the destination vertices.

For example, for graph (a) shown below, assume the starting vertex is 1, and the set of destination vertices is {5,6}, then graph (b) shows a minimum covering tree.

                   graph and tree


Input Formats

An input file for LP systems contains the following facts:
An input file for Minizinc specifies the size of the graph (graph_size), the starting vertex (start), the number of destinations (n_dests), an array of destination vertices (dest), the number of edges (n_edges), and three arrays that define the edge relation (from, to, and cost).

Output format

The output should contain exactly one fact of the form min_cost(K), where K is the travel cost of a minimum tree of the given graph that covers the starting vertex and the destination vertices. For ASP systems, the output may consist of multiple answer sets, and only the final one is treated as a solution.

Samples


LP InputMinizinc InputOutput
graph_size(6).
start(1).
dest(6).
edge(1,2,4).
edge(1,3,2).
edge(2,3,5).
edge(2,4,10).
edge(3,5,3).
edge(4,5,4).
edge(4,6,11).
graph_size = 6;
start = 1;
n_dests = 1;
dest = [6];
n_edges = 7;
from = [1,1,2,2,3,4,4];
to = [2,3,3,4,5,5,6];
cost = [4,2,5,10,3,4,11];

min_cost(20).
graph_size(6).
start(1).
dest(5).
dest(6).
edge(1,2,4).
edge(1,3,2).
edge(2,3,5).
edge(2,4,10).
edge(3,5,3).
edge(4,5,4).
edge(4,6,11).
graph_size = 6;
start = 1;
n_dests = 2;
dest = [5,6];
n_edges = 7;
from = [1,1,2,2,3,4,4];
to = [2,3,3,4,5,5,6];
cost = [4,2,5,10,3,4,11];

min_cost(20).
graph_size(6).
start(1).
dest(5).
dest(6).
edge(1,2,6).
edge(1,3,1).
edge(1,4,5).
edge(2,3,5).
edge(2,5,3).
edge(3,4,5).
edge(3,5,6).
edge(3,6,4).
edge(4,6,2).
graph_size = 6;
start = 1;
n_dests = 2;
dest = [5,6];
n_edges = 9;
from = [1,1,1,2,2,3,3,3,4];
to = [2,3,4,3,5,4,5,6,6];
cost = [6,1,5,5,3,5,6,4,2];

min_cost(11).