Hello, I have tried anything suggested before and still got WA
Here is my code
Code: Select all
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long LL;
#define INF 1000000000
#define PI 3.14159265
#define FOR(i,a,n) for(int i=a,_n=n; i<_n; i++)
#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)
#define DEBUG(x) cout << '>' << #x << ':' << x << '\n';
int arr[55][55];
int n_store;
int price[15];
int memo[1<<12][15];
map <int, int> store;
int f(int aa, int last){
if ( memo[aa][last] != -1 ) return memo[aa][last];
int ret = 0;
FOR (i, 0, n_store){
if ( ( (1<<i) | aa ) == aa ) continue;
int next = store[i]; int prev = store[last];
int benefit = f(( 1<<i) | aa, i) + price[i] - arr[prev][next];
if ( benefit > ret ) ret = benefit;
}
if ( ret == 0 ) ret -= arr[store[last]][0];
return memo[aa][last] = ret;
}
int main(){
int t; scanf("%d", &t);
while (t--){
memset(memo, -1, sizeof memo);
store.clear();
FOR (i, 0, 55) FOR (j, 0, 55) arr[i][j] = INF;
FOR (i, 0, 55) arr[i][i] = 0;
int n, m; scanf("%d %d", &n, &m);
FOR (i, 0, m){
int a, b, xx, yy;
scanf("%d %d %d.%d", &a, &b, &xx, &yy);
int temp = (xx*100) + yy;
arr[a][b] = min(arr[a][b], temp);
arr[b][a] = min(arr[b][a], temp);
}
FOR (k, 0, n+1){
FOR (i, 0, n+1){
FOR (j, 0, n+1){
arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);
}
}
}
scanf("%d", &n_store);
FOR (i, 0, n_store){
int xx, yy, a;
scanf("%d %d.%d",&a, &xx, &yy);
store[i] = a;
price[i] = (xx*100) + yy;
}
int ret = 0;
FOR (i, 0, n_store){
int next = store[i];
int benefit = f(1<<i, i) + price[i] - arr[0][next];
if ( benefit > ret )ret = benefit;
}
if ( ret <= 0 ) puts("Don't leave the house");
else{
int xx = ret/100; int yy = ret%100;
printf("Daniel can save $%d.%02d\n", xx, yy);
}
}
return 0;
}
Is there any critical input that i might miss? thx before
