백준 9205 맥주 마시면서 걸어가기

백준 9205
50m 당 맥주 한병씩 총 20병씩 박스에 담아둘 수 있으므로 총 1000m씩 갈 수 있다. 편의점에 가기만 하면 계속해서 20병씩 채워두면 되기 때문에 방문하는 곳마다 1000미터 이내에 편의점이 있으면 큐에 넣고 페스티벌에 도착할 수 있으면 끝내면 된다.

#include<bits/stdc++.h>
using namespace std;
int t, n;
int x, y;
int x1, y2;
vector<pair<int, int>> v;

int vis[105];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	 
	cin >> t;

	while (t--) {
		vector<tuple<int, int, int>> v1;
		int flag = 0;
		cin >> n;

		cin >> x >> y;

		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			v.push_back({ a,b });
			v1.push_back({ abs(x - a) + abs(y - b),a,b });
		}
		sort(v1.begin(), v1.end());
		cin >> x1 >> y2;

		queue<pair<int, int>> q;
		q.push({ x,y });
		while (!q.empty()) {

			auto cur = q.front();
			q.pop();

			if (abs(cur.first-x1) + abs(cur.second- y2)<=1000) {
				cout << "happy" << '\n';
				flag = 1;
				break;
			}

			for (int i = 0; i < n; i++) {
			
				int nx = get<1>(v1[i]);
				int ny = get<2>(v1[i]);

				if (abs(cur.first - nx) + abs(cur.second - ny) > 1000|| vis[i]) continue;	
				q.push({ nx,ny });
				vis[i] = 1;
			}
		}
		if(!flag) cout << "sad" << '\n';
		memset(vis, 0, sizeof(vis));
	}

}