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 0xfffffffffLLlong 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;}
文章定位: