백준 22865 - 가장 먼 곳(C++)

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

22865번: 가장 먼 곳

다익스트라를 이용하는 문제입니다.

1 ~ N까지 중에서, 친구의 위치가 3개가 주어질 때, 최소 거리가 가장 긴 위치를 찾는 문제입니다.

1부터 시작해 1->1 ~ 1->N,,,,,,N->1 ~ N->N까지 모든 경우를 구한 뒤,
3지점까자의 각각의 거리를 비교해서 최솟값을 찾는 것은 다익스트라를 100,000번 돌려야 되기 때문에 시간초과가 생기게 됩니다.

따라서, 다른 방법으로 3개의 친구 위치에서 다익스트라를 통해 1~N까지의 거리를 구한 뒤, 이를 비교해주면
다익스트라를 3번만 돌리면 되기에 훨씬 시간이 줄어들게 됩니다.  


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

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

using namespace std;

int N, M;
int Friend[3];
LL Distance[100001][3];
vector<pair<int, int>> connect[100001];
priority_queue<pair<LL, int>, vector<pair<LL, int>>> q;

LL Min(LL x, LL y, LL z){
	LL mini = min(x, y);
	mini = min(mini, z);
	return mini;
}

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

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

void solve(){
	LL mini = -INF;
	int Point;
	for(int i = 0; i < 3; i++){
		Dijstra(Friend[i], i);
	}
	for(int i = 1; i <= N; i++){
		LL Dis = Min(Distance[i][0], Distance[i][1], Distance[i][2]);
		if(mini < Dis){
			mini = Dis;
			Point = i;
		}
	}
	cout << Point;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 0; i < 3; i++) cin >> Friend[i];
	cin >> 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});
	}
	solve();
	return 0;
}

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