[백준/BOJ] 백준 13911번 : 집 구하기

https://www.acmicpc.net/problem/13911

13911번: 집 구하기

 

맥도날드들의 위치와, 스타벅스들의 위치에서 다익스트라 알고리즘을 이용하여 각 정점까지 최단거리 탐색을 해 나아가면서, 각 정점마다 맥도날드에서 해당 정점까지 최소거리, 스타벅스에서 해당 정점까지 최소거리를 구한 뒤, 각 정점을 확인해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int v, e;
vector<pair<int, int>> adj[10005];
vector<int> mcd(10005, 0);
vector<int> star(10005, 0);
int m, x;
int s, y;

int solve() {

	vector<int> mcd_len(10005, 987654321); //맥도날드에서 해당 위치까지 최소 거리
	vector<int> star_len(10005, 987654321); //스타벅스에서 해당 위치까지 최소 거리

	priority_queue<tuple<int, int, int>> pq; //(-cost, 0:맥도날드 1:스타벅스, 위치)

	for (int i = 1; i <= v; i++) {
		if (mcd[i] == 1) {
			mcd_len[i] = 0;
			pq.push(make_tuple(-0, 0, i));
		}
		if (star[i] == 1) {
			star_len[i] = 0;
			pq.push(make_tuple(-0, 1, i));
		}
	}

	while (!pq.empty()) {
		int here_cost = -get<0>(pq.top());
		int type = get<1>(pq.top());
		int here = get<2>(pq.top());
		pq.pop();

		if (type == 0) { //맥도날드일때

			if (here_cost > x) {
				continue;
			}
			if (here_cost > mcd_len[here]) {
				continue;
			}

		}

		else { //스타벅스일때

			if (here_cost > y) {
				continue;
			}
			if (here_cost > star_len[here]) {
				continue;
			}
		}

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (type == 0) { //맥도날드일때

				if (there_cost < mcd_len[there]) {
					mcd_len[there] = there_cost;
					pq.push(make_tuple(-there_cost, type, there));
				}

			}

			else { //스타벅스일때

				if (there_cost < star_len[there]) {
					star_len[there] = there_cost;
					pq.push(make_tuple(-there_cost, type, there));
				}

			}

		}
	}

	int result = 987654321;
	for (int i = 1; i <= v; i++) {

		if (mcd[i] == 0 && star[i] == 0 && mcd_len[i] <= x && star_len[i] <= y) {
			result = min(result, mcd_len[i] + star_len[i]);
		}
	}

	if (result == 987654321) {
		return -1;
	}

	return result;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> v >> e;

	for (int i = 0; i < e; i++) {
		int u, v, w;
		cin >> u >> v >> w;

		adj[u].push_back(make_pair(w, v));
		adj[v].push_back(make_pair(w, u));
	}

	cin >> m >> x;

	for (int i = 0; i < m; i++) {
		int input;
		cin >> input;
		mcd[input] = 1;
	}

	cin >> s >> y;

	for (int i = 0; i < s; i++) {
		int input;
		cin >> input;
		star[input] = 1;
	}

	cout << solve();

	return 0;
}