[BOJ/Gold 2] 백준 13911 집 구하기(C++)

문제 링크

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

13911번: 집 구하기

 

문제

안양에 사는 상혁이는 4년간의 통학에 지쳐 서울에 집을 구하려고 한다. 상혁이가 원하는 집은 세가지 조건이 있다.

• 맥세권 : 맥세권인 집은 맥도날드와 집 사이의 최단거리가 x이하인 집이다.
• 스세권 : 스세권인 집은 스타벅스와 집 사이의 최단거리가 y이하인 집이다.
• 맥세권과 스세권을 만족하는 집 중 최단거리의 합이 최소인 집

통학 때문에 스트레스를 많이 받은 상혁이는 집을 선택하는 데 어려움을 겪고 있다. 똑똑한 여러분이 상혁이 대신 이 문제를 해결해 주자. 이사 갈 지역의 지도가 그래프로 주어지고 맥도날드와 스타벅스의 위치가 정점 번호로 주어질 때 상혁이가 원하는 집의 최단거리의 합을 출력하는 프로그램을 작성하시오. (맥도날드와 스타벅스가 아닌 정점에는 모두 집이 있다.)

위의 예제 지도에서 사각형은 맥도날드를, 별은 스타벅스가 위치한 정점을 나타낸다. 각 원은 집이 있는 정점을 낸다. x가 6이고 y가 4일 때 가능한 집의 정점은 6이다. 맥도날드까지의 최단거리가 2, 스타벅스까지의 최단거리가 4로 총 합이 6이 되기 때문이다. 정점 7은 맥세권이면서 스세권이지만 맥도날드까지의 최단거리가 6, 스타벅스까지의 최단거리가 2로 총 합이 8로써 정점 6의 값보다 크므로 답이 아니다. 그 외의 정점 2, 3, 4는 맥세권이면서 스세권인 조건을 충족하지 못하므로 답이 될 수 없다.

입력

첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사이에 가중치가 w(1 ≤ w < 10,000)인 도로가 존재한다는 뜻이다. u와 v는 서로 다르며 다른 두 정점 사이에는 여러 개의 간선이 존재할 수도 있음에 유의한다. E+2번째 줄에는 맥도날드의 수 M(1 ≤ M ≤ V-2) 맥세권일 조건 x(1 ≤ x ≤ 100,000,000)가 주어지고 그 다음 줄에 M개의 맥도날드 정점 번호가 주어진다. E+4번째 줄에는 스타벅스의 수 S(1 ≤ S ≤ V-2)와 스세권일 조건 y(1 ≤ y ≤ 100,000,000)가 주어지고 그 다음 줄에 S개의 스타벅스 정점 번호가 주어진다. 

• 맥도날드나 스타벅스가 위치한 정점에는 집이 없다.
• 한 정점에 맥도날드와 스타벅스가 같이 위치할 수 있다.
• 집이 있는(= 맥도날드나 스타벅스가 위치하지 않은) 정점이 하나 이상 존재한다.

출력

 상혁이가 원하는 집의 맥도날드까지의 최단거리와 스타벅스까지의 최단거리 합을 출력한다. 만일 원하는 집이 존재하지 않으면 -1을 출력한다.

예제 입력 1

8 11
1 2 2
1 4 1
2 4 2
2 3 1
2 7 8
3 7 3
4 5 2
4 6 1
6 7 6
6 8 4
7 8 2
2 6
1 5
1 4
8

예제 출력 1

6

알고리즘 분류

• 최단 거리 알고리즘

풀이

맥도날드가 있는 위치 M개를 시작점으로 잡고 다익스트라를 수행하고, 스타벅스가 있는 위치 S개를 시작점으로 잡고 다익스트라를 수행하여 총 2번의 다익스트라를 수행한다.

그리고 맥세권과 스세권인 집이 있는 위치 중 맥도날드와 스타벅스까지의 거리의 합의 최솟값을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10001
#define LL long long
#define INF 3e9

using namespace std;
int V, E, M, X, S, Y;
vector<pair<int, LL> > Edge[MAX];
priority_queue<pair<LL, int> > PQ;
LL Cost[2][MAX];
bool isHouse[MAX];
LL answer = INF * 2;

void Input() {
	cin >> V >> E;
	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= V; j++) {
			Cost[i][j] = INF;
		}
	}
	for (int i = 0; i < E; i++) {
		int A, B;
		LL C;
		cin >> A >> B >> C;
		Edge[A].push_back(make_pair(B, C));
		Edge[B].push_back(make_pair(A, C));
	}
}

void Dijkstra(int I) {
	while (!PQ.empty()) {
		LL CurCost = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		if (Cost[I][CurX] < CurCost) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			LL nextCost = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (Cost[I][nextX] > CurCost + nextCost) {
				Cost[I][nextX] = CurCost + nextCost;
				PQ.push(make_pair(-Cost[I][nextX], nextX));
			}
		}
	};
}

void Settings() {
	cin >> M >> X;
	for (int i = 0; i < M; i++) {
		int A;
		cin >> A;
		isHouse[A] = true;
		Cost[0][A] = 0;
		PQ.push(make_pair(0, A));
	}
	Dijkstra(0);
	cin >> S >> Y;
	for (int i = 0; i < S; i++) {
		int A;
		cin >> A;
		isHouse[A] = true;
		Cost[1][A] = 0;
		PQ.push(make_pair(0, A));
	}
	Dijkstra(1);
}

void Find_Answer() {
	for (int i = 1; i <= V; i++) {
		if ((!isHouse[i]) && (Cost[0][i] <= X) && (Cost[1][i] <= Y)) {
			answer = min(answer, Cost[0][i] + Cost[1][i]);
		}
	}
	if (answer == INF * 2) {
		cout << -1 << "\n";
	}
	else {
		cout << answer << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}