[BOJ/Gold 2] 백준 14618 총깡 총깡(C++)

문제 링크

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

14618번: 총깡 총깡

 

문제

동물 애호가 진서는 총깡총깡 뛰는 동물과 짝폴짝폴 뛰는 동물들을 K마리씩 키운다. 타지로 취업하게 된 진서는 내일 이사를 한다.

이사하게 될 집에서 같이 살게 될 룸메이트 일호는 동물을 싫어하기 때문에 진서는 근처의 집에 동물들을 한마리씩 맡길 예정이다.

진서가 동물들을 맡길 수 있는 집의 종류는 A형 집과 B형 집 2종류 이다.

우연하게도 짝폴짝폴 뛰는 동물과 총깡총깡 뛰는 동물, A형 집, B형 집의 수는 모두 같다.

진서는 총깡총깡 뛰는 동물들과 짝폴짝폴 뛰는 동물들을 같은 종류의 집에 통일 시켜 맡기고 싶다.

하지만 진서는 총깡총깡 뛰는 동물들을 약간 더 좋아하므로 각 집에서 동시에 출발하여 진서네 집으로 가장 빨리 도착하는 동물이 총깡총깡 뛰는 동물이길 원한다.

진서가 살게 될 집, A형 집, B형 집, A형 집도 B형 집도 아닌 집이 있는 지도가 주어질 때 총깡총깡 뛰는 동물이 A형 집에 살아야 할 지 B형집에 살아야 할지 출력하고 가장 빨리 도착하는 총깡총깡 뛰는 동물이 진서네 집으로 부터 얼마만큼 떨어져 있는지 출력하라.

(만약 총깡총깡 뛰는 동물들이 A형집에 살던 B형집에 살던 상관이 없는 경우는 A형집에 살기로 한다.)

입력

입력의 첫 번째 줄에 전체 집의 수 N과 집과 집사이를 연결하는 도로 M이 공백으로 주어진다. (3 ≤ N ≤ 5,000, 3 ≤ M ≤ 20,000)

입력의 둘째 줄에 진서의 집 J가 주어진다 (1 ≤ J ≤ N)

입력의 셋째 줄에 종류별 동물의 수 K가 주어진다. (2*K ≤ N)

입력의 넷째 줄에 K개의 A형 집이 공백으로 구분되어 주어진다.

입력의 다섯 번째 줄에 K개의 B형 집이 공백으로 구분되어 주어진다.

이후 M개의 줄에 X Y Z(1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)가 주어진다. 이는 X번 집과 Y번 집 사이에 Z의 길이를 가지는 도로가 존재한다는 것이다.

출력

총깡총깡 뛰는 동물이 살게 될 집의 종류를 말한 뒤 다음줄에 거리를 출력한다.

A형 집에서만 진서의 집에 갈 수 있는 경우 A를 출력한 뒤 다음 줄에 거리를 출력, B형 집에서만 진서의 집에 갈 수 있는 경우 B를 출력한 뒤 다음 줄에 거리를 출력, A형 집, B형 집 둘다 진서의 집에 갈 수 없는 경우에는 –1을 출력한다.

예제 입력 1

5 6
2
2
1 4
3 5
1 2 3
1 5 3
1 3 10
2 4 7
2 5 2
3 4 2

예제 출력 1

B
2

알고리즘 분류

• 최단 거리 알고리즘

풀이

K개의 A 집을 시작점으로 하여 다익스트라를 수행하고, K개의 B 집을 시작점으로 하여 다익스트라를 수행해 총 2번의 다익스트라를 수행한다.

그리고 A 집에서 J까지의 최단 거리가 B 집에서 J까지의 최단 거리와 같거나 더 작다면 A 집을 선택하고, 그게 아니라면 B 집을 선택한다.

A 집에서 J까지 도달하지 못 한다면 B 집을 선택하고, B 집에서 J까지 도달하지 못 한다면 A 집을 선택한다.

A 집, B 집 둘 다 도달할 수 없다면 -1을 출력한다.

코드

#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 5001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, J, K, A, B;
vector<pair<int, int> > Edge[MAX];
priority_queue<pair<int, int> > PQ;
int Cost[3][MAX];
int isHouse[MAX];

void Input() {
	cin >> N >> M;
	for (int i = 1; i < 3; i++) {
		for (int j = 1; j <= N; j++) {
			Cost[i][j] = INF;
		}
	}
	cin >> J;
	cin >> K;
	for (int i = 0; i < K; i++) {
		cin >> A;
		isHouse[A] = 1;
	}
	for (int i = 0; i < K; i++) {
		cin >> B;
		isHouse[B] = 2;
	}
	for (int i = 0; i < M; i++) {
		int X, Y, Z;
		cin >> X >> Y >> Z;
		Edge[X].push_back(make_pair(Y, Z));
		Edge[Y].push_back(make_pair(X, Z));
	}
}

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() {
	for (int i = 1; i <= N; i++) {
		if (isHouse[i] == 1) {
			Cost[1][i] = 0;
			PQ.push(make_pair(0, i));
		}
	}
	Dijkstra(1);
	for (int i = 1; i <= N; i++) {
		if (isHouse[i] == 2) {
			Cost[2][i] = 0;
			PQ.push(make_pair(0, i));
		}
	}
	Dijkstra(2);
}

void Find_Answer() {
	if ((Cost[1][J] != INF) && (Cost[2][J] != INF)) {
		if (Cost[1][J] <= Cost[2][J]) {
			cout << "A" << "\n";
			cout << Cost[1][J] << "\n";
		}
		else {
			cout << "B" << "\n";
			cout << Cost[2][J] << "\n";
		}
	}
	else if ((Cost[1][J] == INF) && (Cost[2][J] != INF)) {
		cout << "B" << "\n";
		cout << Cost[2][J] << "\n";
	}
	else if ((Cost[1][J] != INF) && (Cost[2][J] == INF)) {
		cout << "A" << "\n";
		cout << Cost[1][J] << "\n";
	}
	else if ((Cost[1][J] == INF) && (Cost[2][J] == INF)) {
		cout << -1 << "\n";
	}
}

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

	return 0;
}