[백준] 1238번 파티 (C++)

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

전 문제와 마찬가지로 다익스트라 알고리즘을 공부하기 위해 푼 문제이다.
다익스트라 알고리즘에 대한 게시물은 조만간 올릴 예정이다.

priority_queue를 사용해 각 노드까지의 최단거리를 계산해준다.
하지만, 문제에서 왕복에 대한 시간을 계산하는 것이 포인트이다.
따라서, 1~N까지 다익스트라 알고리즘을 적용해서 최단거리를 구해준 다음에 더해주면 된다.

1. 간선에 대한 정보를 vector<pair<int, int>>배열 자료형에 담는다.

2. 1~N까지 for문을 돌리면서 dijkstra 알고리즘을 적용해준다.
   2-1. 이때, i가 목표지점인 x인 경우와 아닌 경우를 따로 생각해야한다.
   2-2. i가 목표지점이 아닌 경우, x까지의 최단거리만 필요하므로 dijkstra 알고리즘을 적용해준 뒤, 별도의 result 배열에 노드에서 x까지의 최단거리만 result[i]의 형태로 저장했다.
   2-3. i가 x인 경우 dijkstra 알고리즘을 돌리면 된다.

3. priority_queue를 사용해서 dijkstra 알고리즘을 적용한다.
   3-1. 처음 노드의 거리를 0으로 지정한 뒤 pq에 삽입한다.
   3-2. distance는 낮은 순서대로 우선순위를 높게 하기위해 -(음수)값으로 지정해준다.
   3-3. pq에서 하나씩 꺼내면서 비교해준다. 최단 거리보다 distance가 높은 경우는 최단거리가 아니므로 생략해준다.
   3-4. 간선 vector를 탐색하면서 최단거리 배열에 있는 값보다, 현재 노드를 거쳐가는 거리가 더 작을 경우, 최단거리 배열을 갱신해준다.

4. 마지막으로 result배열의 값과 i가 x일 때의 최단거리 배열을 더하면서 최대값을 구해주면 된다.

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

int n, m, x;
vector<pair<int, int>> road[1001];
int min_d[1001];
int min_x[1001];
int result[1001];

void dijkstra(int *min_dis, int start) {
	min_dis[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ start, 0 });
	while (!pq.empty()) {
		int distance = -pq.top().second;
		int cur = pq.top().first;
		pq.pop();
		if (min_dis[cur] < distance) continue;
		for (int i = 0; i < road[cur].size(); i++) {
			int next = road[cur][i].first;
			int dis = road[cur][i].second;
			if (min_dis[next] > min_dis[cur] + dis) {
				min_dis[next] = min_dis[cur] + dis;
				pq.push({ next, -min_dis[next] });
			}
		}
	}
}

int main() {
	cin >> n >> m >> x;
	
	for (int i = 0; i < m; i++) {
		int s, e, t;
		cin >> s >> e >> t;
		road[s].push_back({ e, t });
	}
	for(int i = 1; i <= n; i++){
		if (i == x){
			for (int i = 1; i <= n; i++) min_d[i] = 987654321;
			dijkstra(min_d, i);
		}
		else {
			for (int i = 1; i <= n; i++) min_x[i] = 987654321;
			dijkstra(min_x, i);
			result[i] = min_x[x];
		}
	}
	int max_time = 0;
	for (int i = 1; i <= n; i++) {
		max_time = max(max_time, min_d[i] + result[i]);
	}
	cout << max_time;
}