UVa 11284

non-classic TSP problem, Floyd for shortest path and DP are used here
matrix g is used to maintain shortest path of all point pairs
matrix g2 is used to maintain actually cost, because we don't need to traverse all points
state:
    dp[i][j] - maximum money saved when point i is visited, j is the bitmask, all have the same
    meaning with tradition TSP problem except we are maximizing how much money saved
transition:
    dp[i][j]=max(dp[i][j], dp[i][j|(1<<k)], dp[k][j|(1<<k)]-dist2[i][k]+u[k-1])
    because now we have 2 choices, to buy or not to buy at store k

/* UVas */
/*****************************************************************************/
int t, n, m, p;
int main(void) {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        n++;
        double g[n][n];
        for (int i=0; i<n; i++)
            fill(g[i], g[i]+n, (double)INT_MAX);
        for (int i=0; i<m; i++) {
            int a, b;
            double c;
            scanf("%d %d %lf", &a, &b, &c);
            g[a][b]=g[b][a]=min(g[a][b], c);
        }
        scanf("%d", &p);
        int s[p];
        double u[p];
        double g2[p+1][p+1];
        double d[p+1][1<<(p+1)];
        for (int i=0; i<p; i++)
            scanf("%d %lf", &s[i], &u[i]);
        /* Floyd */
        for (int k=0; k<n; k++)
            for (int i=0; i<n; i++)
                for (int j=0; j<n; j++)
                    g[i][j]=min(g[i][j], g[i][k]+g[k][j]);
        /**/
        for (int i=0; i<p; i++)
            g2[0][i+1]=g2[i+1][0]=g[0][s[i]];
        for (int i=1; i<=p; i++)
            for (int j=1; j<=p; j++)
                g2[i][j]=g[s[i-1]][s[j-1]];
        for (int i=0; i<p+1; i++) {
            fill(d[i], d[i]+(1<<(p+1)), (double)INT_MIN);
            d[i][(1<<(p+1))-1]=-g2[i][0];
        }
        /* TSP */
        for (int mask=(1<<(p+1))-1; mask>=0; mask--)
            for (int i=0; i<p+1; i++)
                if (mask&(1<<i))
                    for (int j=0; j<p+1; j++)
                        if (!(mask&(1<<j)))
                            d[i][mask]=max(d[i][mask], 
                                           max(d[i][mask|(1<<j)],
                                               d[j][mask|(1<<j)]-g2[i][j]+u[j-1]));
        /**/
        (abs(d[0][1])>1e-9)&&(d[0][1]>0)?
        printf("Daniel can save $%.2lf\n", d[0][1]):
        printf("Don't leave the house\n");
    }
}
/*****************************************************************************/