Delivery man P93428


Statement
 

pdf   zip

thehtml

A delivery man works on a city modelled as a graph with n vertices and m bidirectional edges with positive distances. The delivery man has to pick and deliver k objects in order from 1 to k. For each object z ∈ {1, …, k}, he has this information:

  • the vertex pz where the object must be picked;
  • the vertex dz where the object must be delivered, with dzpz;
  • the order oz to deliver the object.

The set {oz} is a permutation of {1, …, k}. For instance, if k = 3, o1 = 3, o2 = 1 and o3 = 2, then the objects must be delivered in this order: 2, 3 and 1. In this case, the delivery man has to pick object ‍1 and afterwards pick object 2. Then, he can decide to pick object 3, or alternatively to deliver object 2. If he decides to deliver object 2, then he has to pick object 3, and so on.

What is the minimum total time to deliver all the objects? The delivery man can choose where to begin and where to end his journey. Assume that the time to pick and deliver objects is neglectable, and that the delivery man can carry as many objects as he wants.

Input

Input consists of several cases. Each case begins with n and m, followed by m triples x y c indicating an edge between x and y with cost c, where xy. Follow k, and the k triples pz ‍dz ‍oz in order from 1 to k. Assume 2 ≤ n ≤ 1000, n − 1 ≤ m ≤ 5n, that vertices are numbered starting at 0, 1 ≤ c ≤ 109, that the graph is connected, that there is at most one edge between each pair of vertices, and 1 ≤ k ≤ 50.

Output

For each case, print the minimum cost to deliver all the objects.

Public test cases
  • Input

    5 6  0 1 10  0 4 3  1 2 2  1 3 1  1 4 2  2 4 3
    2  0 1 2  2 3 1
    2 1  1 0 1000000000
    3  1 0 3  0 1 2  1 0 1
    3 2  1 2 9  1 0 12
    2  1 2 1  0 1 2
    

    Output

    10
    5000000000
    42
    
  • Information
    Author
    Edgar Moreno
    Language
    English
    Official solutions
    C++
    User solutions
    C++