HDU 4284 Travel / 狀態壓縮DP

最多15個必須經過的城市 2進制表示

dp[i][j] 表示i這個狀態下現在位置是第j個城市剩下的最大錢數

我日啊 id有一個錯了 害我哇了12次 一發現一改馬上AC 傷不起

#include 
#include 
#include 
using namespace std;
const int maxn = 110;
int INF = 999999999;
struct Li
{
	int u, c, d;
}b[maxn];
int dp[1<<16][16];
int a[maxn][maxn];
int id[maxn];
int n, m, h, Money;
void floyd()
{
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
		 		if(a[i][k] + a[k][j] < a[i][j])
		 			a[i][j] = a[i][k] + a[k][j];
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d %d", &n, &m, &Money);
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				if(i == j)
					a[i][j] = 0;
				else
					a[i][j] = INF;
			}
		}
		memset(id, 0, sizeof(id));
		while(m--)
		{
			int u, v, w;
			scanf("%d %d %d", &u, &v, &w);
			if(a[u][v] > w)
			{
				a[u][v] = w;
				a[v][u] = w;
			}
		}
		scanf("%d", &h);
		for(int i = 0; i < h; i++)
		{
			scanf("%d %d %d", &b[i].u, &b[i].c, &b[i].d);
			id[i] = b[i].u;
		}
		
		memset(dp, -1, sizeof(dp));
		floyd();
		for(int i = 1; i < (1<= 0)
							dp[i][j] = Money - a[1][id[j]] - b[j].d + b[j].c;
						
						continue;
					}
					for(int k = 0; k < h; k++)
					{
						if((i&(1<= 0)
							{
								dp[i][j] = max(dp[i][j], dp[i^(1<= 0)
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}