SWEA 2383 점심 식사시간

코드:

/* 1. 바로 다음(next(it))이 아니라 this trhead보다 큰 tm 필드를 지니는 thread 선택해야 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<pair<int, int>> hm;
vector<pair<int, int>> ext;
vector<int> extn;
bool cbn[10];
int ans;

struct thrd {
	int tm;
	bool job;
	int hmn;
	bool wait;
};

struct oprt {
	bool operator()(const thrd &a, const thrd &b) const {
		if (a.tm == b.tm) {
			if (a.job == b.job) {
				return a.hmn < b.hmn;
			}
			return a.job > b.job;
		}
		return a.tm < b.tm;
	}
};
set<thrd, oprt> q;

int main() {
	int T; cin >> T;
	for (int tc = 1; tc <= T; ++tc) {
		int N; cin >> N;
		hm.clear(); ext.clear(); extn.clear();
		for (int r = 0; r < N; ++r) {
			for (int c = 0; c < N; ++c) {
				int obj; cin >> obj;
				if (obj == 1) {
					hm.emplace_back(r, c);
				}
				else if (obj > 1) {
					ext.emplace_back(r, c);
					extn.push_back(obj);
				}
			}
		}

		ans = 1000000000;
		for (int r = 0; r <= hm.size(); ++r) {
			fill(cbn, cbn + hm.size() - r, 0);
			fill(cbn + hm.size() - r, cbn + hm.size(), 1);
			do {
				// construct queue
				q.clear();
				for (int e = 0; e < hm.size(); ++e) {
					int dst = abs(hm[e].first - ext[cbn[e]].first) + abs(hm[e].second - ext[cbn[e]].second);
					q.insert({dst, 0, e, 1});
				}

				int ready = hm.size(); int run[2] = { 0 };
				for (auto it = q.begin(); it != q.end() && ready;) {
					switch (it->job) {
					case 0:
						if (run[cbn[it->hmn]] < 3) {
							++run[cbn[it->hmn]];
							q.insert({ it->tm + extn[cbn[it->hmn]] + it->wait, 1, it->hmn, 0 });
							--ready;
							q.erase(it++);
						}
						else {
							thrd *th = new thrd(*it);
							auto tit = it;
							for (; tit != q.end() && tit->tm == it->tm; ++tit);	/* 1 */
							th->tm = tit->tm;
							th->wait = 0;
							q.insert(*th);
							q.erase(it++);
						}
						break;
					case 1:
						--run[cbn[it->hmn]];
						q.erase(it++);
						break;
					}
				}

				if (q.rbegin()->tm < ans)
					ans = q.rbegin()->tm;
			} while (next_permutation(cbn, cbn + hm.size()));
		}
		cout << '#' << tc << ' ' << ans << '\n';
	}

	return 0;
}