백준 17270 - 연예인은 힘들어(C++)

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

17270번: 연예인은 힘들어

다익스트라를 이용해 풀 수 있는 문제였습니다.

지헌이와 성하가 만날 때, 최적의 장소를 구하는 문제입니다.

최적의 장소는 구하는 방법은
1. 둘이 만날 때, 거리는 최소가 되어야 합니다.
2. 출발지는 장소 후보에서 제외됩니다.
3. 지헌이가 성하보다 더 일찍 도착해야 합니다.
4. 위의 조건을 모두 만족하는 장소가 있다면, 지헌이한테 가장 가까운 곳이 선정됩니다.

정점이 100개까지 주어지기 때문에, 100개의 점을 모두 확인하면서 최적의 점을 구하는 방법은 너무 비효울 적입니다.
따라서, 이를 효율적으로 구하는 방법을 찾아야 하는데, 생각을 해보면,
정점을 하나 정한 뒤, 거리를 구하는 방법은 지헌 -> X + X -> 성하로 구하게 됩니다.
그렇다면, 지헌이가 다른 정점들까지 걸리는 비용과 성하가 다른 정점들까지 걸리는 비용을 따로 구한 뒤,
해당 값들로 구한다면, 2번의 다익스트라로 통해 최소 거리들을 구할 수 있게 됩니다.

이후에는 위의 조건에 맞춰서 후보를 줄이면서 답을 구해주면 됩니다.


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

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

using namespace std;

int N, M;
int J, S;
vector<pair<int, int>> connect[101];
priority_queue<pair<int, int>, vector<pair<int, int>>> q;
int Distance[101];
int J_Distance[101]; //J -> X를 저장
int S_Distance[101]; //S -> X를 저장

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

void Dijstra(int st){
	reset_distance();
	Distance[st] = 0;
	q.push({-Distance[st], st});
	while(!q.empty()){
		int x = q.top().S;
		int 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;
			int n_cost = cost + connect[x][i].S;
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void solve(){
	int JS_distance = INF;
	int Point = -1, J_dis = INF;
	Dijstra(J); // 지헌이부터 출발해 다른 지점까지 걸리는 비용
	for(int i = 1; i <= N; i++){
		J_Distance[i] = Distance[i]; //지헌이를 기준으로 한 값 저장
	}
	Dijstra(S); // 성하부터 출발해 다른 지점까지 걸리는 비용
	for(int i = 1; i <= N; i++){
		S_Distance[i] = Distance[i]; //성하를 기준으로 한 값 저장
	}
	for(int i = 1; i <= N; i++){
		if(i == J || i == S) continue;
		JS_distance = min(JS_distance, J_Distance[i] + S_Distance[i]); // 최소거리를 저장
	}
	for(int i = N; i >= 1; i--){
		if(i == J || i == S) continue;
		if(JS_distance != J_Distance[i] + S_Distance[i]) continue;
		if(J_Distance[i] > S_Distance[i]) continue;
		if(J_dis >= J_Distance[i]){
			J_dis = J_Distance[i];
			Point = i;
		}
	}
	cout << Point;
}

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 >> J >> S;
	solve();
	return 0;
}

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