백준 13911 - 집 구하기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13911

13911번: 집 구하기

다익스트라를 시작할 때, 맥도날드 정점과 스타벅스 정점을 각각 전부 넣고 시작하는 문제였습니다.

맥도날드의 위치들과 스타벅스의 위치들이 주어질 때, 두 가게의 거리의 합이 최소가 되는 지점의 번호를 출력하는 문제입니다.

먼저 맥도날드와 스타벅스로 부터 떨어져 있는 거리를 구해야합니다.
가게가 하나가 아닐 수도 있기에, 어떤 지점을 잡냐에 따라서 거리가 달라질 수 있습니다.
따라서, 이 같은 경우에는 모든 가게의 지점을 넣은 뒤 탐색을 한번이 돌려주면, 집에서부터 가게까지의 최소 거리를 구할 수 있게 됩니다.

스타벅스로부터 떨어진 거리, 맥도날드로부터 떨어진 거리를 구했다면 두 값을 통해
두 가게 거리의 합이 최소가 되는 지점을 찾아주면 됩니다.

먼저, 원하는 집은 두 가게가 위치해 있지 않아야 하며, 떨어진 거리가 X, Y이하여야 합니다.
위 두 조건을 만족하는 집을 찾아, 거리의 합을 구한 뒤, 가장 작은 곳의 위치를 출력해주면 됩니다,

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF LLONG_MAX
#define F first
#define S second

using namespace std;

int N, M;
vector<pair<int, int>> connect[10001];
int mac, X;
int Mac[10001];
int sta, Y;
int Sta[10001];
long long Distance[10001];
long long Mac_distance[10001];
long long Sta_distance[10001];
priority_queue<pair<long long, int>> q;

void reset_distance(){
	for(int i = 1; i <= N; i++) Distance[i] = INF;
}

void Dijstra(){
	while(!q.empty()){
		int x = q.top().S;
		long long cost = -q.top().F;
		q.pop();
		if(Distance[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			long long n_cost = connect[x][i].S + cost;
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void solve(){
	reset_distance();
	for(int i = 1; i <= mac; i++){
		q.push({0, Mac[i]});
		Distance[Mac[i]] = 0;
	}
	Dijstra();
	for(int i = 1; i <= N; i++){
		Mac_distance[i] = Distance[i];
	}
	/////////////////// 맥도날드까지 거리 구하기
	reset_distance();
	for(int i = 1; i <= sta; i++){
		q.push({0, Sta[i]});
		Distance[Sta[i]] = 0;
	}
	Dijstra();
	for(int i = 1; i <= N; i++){
		Sta_distance[i] = Distance[i];
	}
	/////////////////// 스타벅스까지 거리 구하기
	long long ans = INF;
	for(int i = 1; i <= N; i++){
		if(Mac_distance[i] == INF || Sta_distance[i] == INF) continue;
		if(Mac_distance[i] == 0 || Sta_distance[i] == 0) continue;
		if(Mac_distance[i] > X|| Sta_distance[i] > Y) continue;
		ans = min(ans, Mac_distance[i] + Sta_distance[i]);
	}
	if(ans == INF) cout << "-1";
	else cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}	
	cin >> mac >> X;
	for(int i = 1; i <= mac; i++) cin >> Mac[i];
	cin >> sta >> Y;
	for(int i = 1; i <= sta; i++) cin >> Sta[i];
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.