Problem G

SHOPPING TRIP

For some reason, Daniel loves to collect and watch operas on DVD. He can find and order all the operas he wants from Amazon, and they will even deliver them right to his door, but he can usually find a better price at one of his favourite stores. However, with the cost of gas nowadays, it is hard to tell whether or not one would actually save money by driving to the stores to purchase the DVDs.

Daniel would like to buy some operas today. For each of the operas he wants, he knows exactly one store that is selling it for a lower cost than the Amazon price. He would like to know if it would actually be worth it to go out and buy the operas from the stores.

Daniel only knows the road system connecting his favourite stores, and will only use those roads to get around. He knows at least one route, if only an indirect one, to every store.

An example diagram of Daniel's house, his favourite stores, and the roads connecting them.

In his shopping trip, Daniel begins at his house, drives from store to store in any order to purchase his operas, then drives back to his house. For any particular opera, he can opt not to drive to the store to buy it, since he can just order it from Amazon.

For convenience, Daniel assigned his house the integer 0, and numbered each of his favourite stores with integers starting at 1. You are given a description of the road system and the exact amount it would cost for Daniel to drive each road. For each opera Daniel wants, you are given the number of the store it is available at, and the amount he would save if he bought that particular opera at that store. Your task is to determine the greatest amount of money Daniel can save by making the shopping trip.

Input

The first line of input contains a single number indicating the number of scenarios to process. A blank line precedes each scenario.

Each scenario begins with line containing two numbers: N (1 ≤ N ≤ 50), the number of stores, and M (1 ≤ M ≤ 1000), the number of roads. The following M lines each contain a description of a road. Each road is described by two integers indicating the house or stores it connects, and a real number with two decimal digits indicating the cost in dollars to drive that road. All roads are two-way.

The next line in the scenario contains a number P (1 ≤ P ≤ 12), the number of opera DVDs Daniel wants to buy. For each of the P operas, a line follows containing an integer indicating the store number at which the opera is available, and a real number with two decimal digits indicating the difference between the Amazon price and the price at that store in dollars.

Output

For each scenario in the input, write one line of output indicating the largest amount of money, in dollars and cents, that Daniel can save by making his shopping trip. Follow the format of the sample output; there should always be two digits after the decimal point to indicate the number of cents. If Daniel cannot save any money by going to the stores, output a single line saying "Don't leave the house".

Sample Input

2

4 5
0 1 1.00
1 2 3.00
1 3 2.00
2 4 4.00
3 4 3.25
3
2 1.50
3 7.00
4 9.00

1 1
0 1 1.50
1
1 2.99

Output for the Sample Input

Daniel can save $3.50
Don't leave the house


重邊害了我好久 ... 

---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxState 1<<13
#define maxN 13
#define oo 0xfffffffffLL

long long DP[maxState][maxN], map[51][51];
int A[maxN], AD[maxN], best;
int TSP(int state, int n, int last) {

    if(state == 0)    return 0;
    if(DP[state][last] != -oo)    return DP[state][last];
    int i;
    long long max = -oo, tmp;
    for(i = 0; i <= n; i++) {
        if((state&(1<<i)) != 0 && last != i) {
            tmp = TSP(state-(1<<last), n, i);
            tmp -= map[A[i]][A[last]];
            tmp += AD[last];
            if(max < tmp)    max = tmp;
            
        }
    }
    if(state == (1<<last))    max = -map[A[last]][0]+AD[last];
    if(best < max-map[A[last]][0])    best = max-map[A[last]][0];

    DP[state][last] = max;
    return DP[state][last];
}
long long min(long long a, long long b) {
    return a < b ? a : b;
}
int main() {

    int T, x, y;
    int n, m, p, i, j, k, a, b;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i <= n; i++)
            for(j = 0; j <= n; j++)
                map[i][j] = oo;
        for(i = 0; i < m; i++) {
            scanf("%d %d %d.%d", &x, &y, &a, &b);
            map[x][y] = min(100*a+b, map[x][y]);
            map[y][x] = min(100*a+b, map[y][x]);
        }
        scanf("%d", &p);
        int newp, tmpAD[51];
        memset(tmpAD, 0, sizeof(tmpAD));
        for(i = 1; i <= p; i++) {
            scanf("%d %d.%d", &A[i], &a, &b);
            tmpAD[A[i]] += 100*a+b;
        }
        newp = 0;
        for(i = 1; i <= n; i++)
            if(tmpAD[i]) {
                newp++, A[newp] = i, AD[newp] = tmpAD[i];
            }
        p = newp;
        for(k = 0; k <= n; k++)
            for(i = 0; i <= n; i++)
                for(j = 0; j <= n; j++)
                    if(map[i][j] > map[i][k] + map[k][j])
                        map[i][j] = map[i][k] + map[k][j];
        int final = (1<<(p+1))-1;
        for(i = 0; i <= final; i++)
            for(j = 0; j <= p; j++)
                DP[i][j] = -oo;
        map[0][0] = 0;
        best = 0;

        TSP(final, p, 0);
        if(best == 0)
            puts("Don't leave the house");
        else
            printf("Daniel can save $%d.%02d\n", best/100, best%100);
    }
    return 0;
}