[C/C++] 백준 - 13911번 (집 구하기)

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을 출력한다.

2개나 배울 수 있던 좋은 문제이다.

일단 첫 번째로 더미 노드를 이용한 문제 풀이 방법을 배울 수 있었다.

더미 노드란, 데이터 저장을 위한 노드가 아니라 노드의 추가/삭제 구현의 간편성을 위해 사용하는 노드이다. 실제 데이터를 저장하는 다른 노드를 가리키는 포인터의 역할만을 수행한다. 맥도날드와 스타벅스에 맥세권 스세권을 쉽게 구하기 위해 더미 노드를 이용한다. 

 

그리고 INF의 범위,, 이걸 이제야 배웠다는 거부터 공부를 기초부터 제대로 안했다는 증거이다. 

INF범위가 처음에 오버플로우가 발생하는 큰 수를 넣었다가 이걸 해결 못했다. 틀렸습니다 오류 안에서 뜨는 걸보고 바꿔서 제출해봤는데 맞았다고 떴다. 종만북에서도 INF는 987654321 사용을 권장한다고 했는데 그 부분을 다시 봐야겠다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

typedef struct GraphNode {
	int dest;
	int cost;
	GraphNode* next;
}GraphNode;

typedef struct Graph {
	GraphNode* adj;
}Graph;

int V, E;
priority_queue<pair<int, int>, vector<pair<int, int>>> pq;

void Init_Graph(Graph* gph, int count) {
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * (count + 3));
	for (int i = 1; i <= count; i++) {
		gph->adj[i].next = NULL;
	}
}

void Reset(Graph* gph, int count) {
	for (int i = 1; i <= count; i++) {
		gph->adj[i].next = NULL;
		free(gph->adj[i].next);
	}
}

int AddDirectedLinked(Graph* gph, int src, int dst, int cost) {
	GraphNode* Temp = (GraphNode*)malloc(sizeof(GraphNode));
	Temp->cost = cost;
	Temp->dest = dst;
	Temp->next = gph->adj[src].next;
	gph->adj[src].next = Temp;
	return 1;
}

int AddUnDirectedLinked(Graph* gph, int src, int dst, int cost) {
	return AddDirectedLinked(gph, src, dst, cost) && AddDirectedLinked(gph, dst, src, cost);
}

void Dijkstra(Graph* gph, vector<int>& dist) {
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int node = pq.top().second;
		pq.pop();

		GraphNode* head = gph->adj[node].next;
		while (head) {
			if (head->cost + cost < dist[head->dest]) {
				dist[head->dest] = head->cost + cost;
				pq.push({ -(head->cost + cost), head->dest });
			}
			head = head->next;
		}
	}
}

int main() {
	fastio;
	Graph graph;
	cin >> V >> E;
	Init_Graph(&graph, V);

	int a, b, c;
	while (E--) {
		cin >> a >> b >> c;
		AddUnDirectedLinked(&graph, a, b, c);
	}

	int M, x, S, y;
	cin >> M >> x;
	vector<int> dist1(V+1, INF);
	for (int i = 0; i < M; i++) {
		int mac; cin >> mac;
		dist1[mac] = 0;
		pq.push({ 0, mac });
	}
	Dijkstra(&graph, dist1);

	cin >> S >> y;
	vector<int> dist2(V+1, INF);
	for (int i = 0; i < S; i++) {
		int star; cin >> star;
		dist2[star] = 0;
		pq.push({ 0, star });
	}
	Dijkstra(&graph, dist2);

	int answer_node=-1, answer_dist = INF;
	for (int node = 1; node <= V; node++) {
		if (dist1[node] && dist2[node] && dist1[node] <= x && dist2[node] <= y)
			answer_dist = answer_dist < dist1[node] + dist2[node] ? answer_dist : dist1[node] + dist2[node];
	}

	if (answer_dist != INF)
		cout << answer_dist << endl;
	else
		cout << -1 << endl;
	
	return 0;
}