취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13911번 문제인 집 구하기이다.
문제는 아래 링크를 확인하자.

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

각 집 노드에서 가장 가까운 맥도날드 노드까지의 최단거리는 각 맥도날드 노드들을 출발점으로 하는 multi-source dijkstra 알고리즘을 이용해 한번에 구해낼 수 있다. 이는 각 집 노드에서 가장 가까운 스타벅스 노드까지의 최단거리 또한 마찬가지이다.

위의 값을 구한 뒤, 맥도날드 노드와 스타벅스가 아닌 노드 중 맥도날드까지의 최단거리가 x 이하, 스타벅스까지의 최단거리가 y 이하인 노드들을 살펴보면서 두 거리의 합의 최솟값을 구해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int N, E, M, S, boundM, boundS;
vector<pair<int, int>> G[10001];
ll distM[10001], distS[10001];

void dijkstraM() {
	int K; cin >> K >> boundM;
	priority_queue<pair<ll, int>> pq;
	while (K--) {
		int x; cin >> x;
		distM[x] = 1;
		pq.push(make_pair(-1, x));
	}

	while (!pq.empty()) {
		ll d = -pq.top().first; int cur = pq.top().second; pq.pop();
		if (d > distM[cur]) continue;
		for (auto& e : G[cur]) {
			int nxt = e.first; ll dd = d + e.second;
			if (distM[nxt] == 0 || dd < distM[nxt]) {
				distM[nxt] = dd;
				pq.push(make_pair(-dd, nxt));
			}
		}
	}
}

void dijkstraS() {
	int K; cin >> K >> boundS;
	priority_queue<pair<ll, int>> pq;
	while (K--) {
		int x; cin >> x;
		distS[x] = 1;
		pq.push(make_pair(-1, x));
	}

	while (!pq.empty()) {
		ll d = -pq.top().first; int cur = pq.top().second; pq.pop();
		if (d > distS[cur]) continue;
		for (auto& e : G[cur]) {
			int nxt = e.first; ll dd = d + e.second;
			if (distS[nxt] == 0 || dd < distS[nxt]) {
				distS[nxt] = dd;
				pq.push(make_pair(-dd, nxt));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> E;
	while (E--) {
		int x, y, w; cin >> x >> y >> w;
		G[x].emplace_back(make_pair(y, w));
		G[y].emplace_back(make_pair(x, w));
	}

	dijkstraM(), dijkstraS();

	ll ans = 1000000000000000007LL;
	for (int i = 1; i <= N; i++) {
		if (distM[i] <= 1 || distM[i] > boundM + 1 || distS[i] <= 1 || distS[i] > boundS + 1) continue;
		ans = min(ans, distM[i] + distS[i] - 2);
	}

	if (ans == 1000000000000000007LL) cout << -1;
	else cout << ans;
}