백준 17835 - 면접보는 승범이네(C++)

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

17835번: 면접보는 승범이네

다익스트라를 사용하는 문제입니다.
정해진 지점에서 시작을 하지 않는다는 것이 특징이였습니다.

면접 장소가 주어졌을 때, 면접 장소에서 가장 멀리 떨어진 곳을 찾는 문제입니다.

주어진 어느 지점에서 출발하는 것이 아니기 때문에 어디서 시작해야 할지를 찾아야합니다.
만약에 N개의 지점에서 모두 확인해본다면 100,000개의 지점에서 확인하는 것이기에 시간초과가 생기게 됩니다.

따라서, 면접 장소를 출발지점으로 생각해서 출발해주면 됩니다.
하지만, 면접 장소도 100,000개이기에 N번 지점에서 출발하는 것과 똑같다고 생각할 수 있겠지만
지점 하나하나에서 탐색을 통해 확인하는 것이 아닌, 모든 면접 장소를 한번에 큐에 넣은 뒤, 확인하는 것입니다.

그렇다면, 어떤 장소든 항상 가장 가까운 면접 장소를 기준으로 거리가 바뀌기에, 한번의 다익스트라를 사용해도 값을 구할 수 있습니다.



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

#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, K;
vector<pair<int, int>> connect[100001];
long long Distance[100001];
int num[100001];
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 = cost + connect[x][i].S;
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void solve(){
	reset_distance();
	for(int i = 1; i <= K; i++){
		q.push({-0, num[i]});
		Distance[num[i]] = 0;
	}
	Dijstra();
	long long Dis = -INF;
	int ans = 0;
	for(int i = 1; i <= N; i++){
		if(Dis < Distance[i]){
			Dis = Distance[i];
			ans = i;
		}
	}
	cout << ans << "\n" << Dis;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d",&x, &y, &cost);
		connect[y].push_back({x, cost});
	}
	for(int i = 1; i <= K; i++) scanf("%d", &num[i]);
	solve();
	return 0;
}

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