SWEA 제주도 여행

#include <iostream>
#include <string.h>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
int T, N, M;
int adj[35][35];
struct info {
	char tp;
	int tm, st;
};
info atr[35];
int ap;		// 공항
int ht[35], hts;	// 초기화 완료

// dfs
int rt[35];
int msts, mrt[35], mrts;	// 초기화 완료
bool vst[35]; // tc
void bf(int s, int hr, int dy, int sts) {
	bool go_ht = false;
	bool go_ap = false;
	for (int u = 0; u < N; ++u) {
		if (vst[u]) continue;						// u가 관광지가 아니면 skip
		int nhr = hr + adj[rt[s - 1]][u] + atr[u].tm;	// u에 가서 노는 시간 갱신
		if (dy == M - 1) {
			go_ap = 1;
			continue;
		}
		if (nhr > 540) {								// 시간 초과
			go_ht = 1;
			continue;
		}
		rt[s] = u;
		vst[u] = 1;
		bf(s + 1, nhr, dy, sts + atr[u].st);
		vst[u] = 0;
	}
	if (go_ap) {
		if (hr + adj[rt[s - 1]][ap] < 540 && sts > msts) {
			msts = sts;
			memcpy(mrt, rt, sizeof(int)*s);
			mrt[s] = ap;
			mrts = s + 1;
		}
	}
	if (go_ht) {
		f(h, hts) {
			if (hr + adj[rt[s - 1]][ht[h]] < 540) {		// 호텔 가는 시간 허락 한다면 /* 1 */
				rt[s] = ht[h];							// 호텔로
				bf(s + 1, 0, dy + 1, sts);			// u방문 보류
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
		cin >> N >> M;
		f(r, N) for(int c = r + 1; c < N; ++c) {
			int a; cin >> a;
			adj[c][r] = adj[r][c] = a;
		}
		
		hts = 0;
		f(n, N) {
			cin >> atr[n].tp;
			switch (atr[n].tp) {
			case 'A': ap = n; vst[n] = 1; break;
			case 'P': cin >> atr[n].tm >> atr[n].st; break;
			case 'H': ht[hts++] = n; vst[n] = 1; break;
			}
		}

		msts = 0;
		rt[0] = ap;
		bf(1, 0, 0, 0);
		cout << '#' << tc << ' ' << msts << ' ';
		for(int r = 1; r < mrts; ++r)
			cout << mrt[r] + 1 << ' ';
		cout << '\n';
	}
	return 0;
}