HDU 4284 상 압 dp + spfa

제목:
n 개의 점 m 줄 무 방향 d 원 을 지정 합 니 다.
아래 m 줄 은 각 변 u < = > v 및 소비 w 를 표시 합 니 다.
아래 top
아래 top 줄
num c d 는 num 로 표 시 된 도시 임금 이 c 건강 증 가격 이 d 라 고 표시 합 니 다.
목 표 는 주어진 top 개 도 시 를 거 쳐 이 도시 에 도 착 했 을 때 즉시 이 도시 의 건강 증 을 구 매 하고 아르 바 이 트 를 해서 돈 을 벌 어야 한다 (도시 당 1 회 만 아르 바 이 트 를 한다).
-- 1 도시 에서 출발 해 마지막 으로 1 도시 로 돌아 가면 건강 증 을 모두 모 을 수 있 나
생각:
top 가 매우 작 기 때문에 상 압 dp
dp [i] [tmp] 는 현재 i 점 에서 도 시 를 거 친 상태 가 tmp 일 때 가장 많은 돈 을 가지 고 있다 는 것 을 나타 낸다.
먼저 dis 배열 플 로 이 드 에 게 최 단 로 를 뛰 어 내 린 뒤 알몸 으로 이동 했다.

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define ll int
#define inf 100000000
#define N 101

int dp[15][1<<15];
int go[N];
int n, m, d;
int dis[N][N];
int C[N], D[N];
int Stack[N], top;
void floyd(){	
	for(int z = 1; z <= n; z++)dis[z][z] = 0;
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)if(dis[i][k] !=inf && i!=k)
			for(int j = 1; j <= n; j++)if(dis[k][j]!=inf && j!=i && j!=k)
				dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}
void init(){
	memset(dp, -1, sizeof dp);
	for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dis[i][j] = inf;
}
struct node{
	int u, t, mon;
	node(int a=0,int b=0,int c=0):u(a),t(b),mon(c){}
};
void BFS(){
	queue<node>q;
	for(int i = 0; i < top; i++) if(d - dis[1][Stack[i]] - D[i]>=0)
		q.push(node(Stack[i], go[Stack[i]], d-dis[1][Stack[i]]-D[i]+C[i]));

	while(!q.empty())
	{
		node a = q.front(); q.pop();
		for(int i = 0; i < top; i++){
			int v = Stack[i];
			if(a.t & go[v])continue;
			node now = a; now.t |= go[v];
			if(dp[i][now.t]==-1 && now.mon - dis[a.u][v] - D[i] >= 0)
			{
				now.mon = now.mon - dis[a.u][v] - D[i] + C[i];
				dp[i][now.t] = now.mon;
				q.push(now);
			}
		}
	}
}
int main()
{
	int i, T, j, u, v, dd;scanf("%d",&T);
	while(T--){
		scanf("%d %d %d",&n,&m,&d);
		init();
		while(m--){
			scanf("%d %d %d",&u,&v,&dd);
			dis[u][v] = dis[v][u] = min(dis[u][v],dd);
		}
		floyd();
		scanf("%d",&top);
		for(i=0;i<top;i++){
			scanf("%d %d %d",&Stack[i],&C[i],&D[i]);
			go[Stack[i]] = 1<<i;
		}
		BFS();
		int ans = -1;
		for(i = 0; i < top; i++)
			ans = max(dp[i][(1<<top)-1] - dis[1][Stack[i]], ans);
		ans>=0?puts("YES"):puts("NO");
	}
	return 0;
}
/*
2 1 1
1 2 1
2
1 100 1
2 1 0

*/