취미로 코딩하기

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

이번에 볼 문제는 백준 22865번 문제인 가장 먼 곳이다.
문제는 아래 링크를 확인하자.

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

A, B, C를 거리가 0인 점으로 설정한 뒤, 가장 먼 점을 dijkstra 알고리즘을 이용하여 구하는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<pair<int,int>> G[100001];
priority_queue<pair<int, int>> pq;

int ans = 999999;
int ansdist = 0;

int dist[100001];
void dijkstra() {
	while (!pq.empty()) {
		int current = pq.top().second, d = -pq.top().first; pq.pop();
		if (dist[current]) continue;
		dist[current] = d;
		if (d > ansdist) {
			ans = current;
			ansdist = d;
		}
		else if (ansdist == d) {
			if (ans > current) ans = current;
		}
		for (auto node : G[current]) {
			if (!dist[node.second]) {
				pq.push({ -(d + node.first),node.second });
			}
		}
	}
}

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

	int N, A, B, C, M; cin >> N >> A >> B >> C >> M;
	while (M--) {
		int x, y, d; cin >> x >> y >> d;
		G[x].push_back({ d,y });
		G[y].push_back({ d,x });
	}
	
	pq.push({ 1,A });
	pq.push({ 1,B });
	pq.push({ 1,C });
	dijkstra();

	cout << ans;
}