[백준 C++] 1238번 : 파티

1. 문제

 

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

1238번: 파티

 

2. 알고리즘 분류

• 그래프 이론
• 데이크스트라

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;

int N, M, X;
vector<pair<int, int>> graph[2][1001];
vector<int> dist[2];

// 데이크스트라 알고리즘(최단거리 구하는 알고리즘)
void Dijstra(int idx) {
	dist[idx][X] = 0;

	// priority_queue를 활용하여 거리가 짧은 순부터 탐색
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> q;
	q.push({ 0, X });

	while (!q.empty()) {
		int min_cost = q.top().first;
		int now = q.top().second;
		q.pop();

		// 기존의 구한 거리가 더 짧으면 넘어가기
		if (min_cost > dist[idx][now]) continue;

		// 현재 정점에서 갈 수 있는 정점 탐색
		for (int i = 0; i < graph[idx][now].size(); i++) {
			int next = graph[idx][now][i].second;
			int next_cost = min_cost + graph[idx][now][i].first;

			// 계산하여 구한 거리가 이전 거리보다 작다면, 갱신
			if (next_cost < dist[idx][next]) {
				dist[idx][next] = next_cost;
				q.push({ next_cost, next });
			}
		}
	}

}

int main() {
	// 입출력 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	// input
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int start, end, time;
		cin >> start >> end >> time;

		// 정방향 그래프 저장
		graph[0][start].push_back({ time, end });
		// 역방향 그래프 저장
		// 각 지점 -> K로 가는 방식에서 각 지점마다 데이크스트라를 통해 최단거리를 구하기 보다는
		// 역방향 그래프를 통해 K -> 각 지점으로 가는 최단거리를 통해 한번에 구하기 위해서
		graph[1][end].push_back({ time, start });
	}

	// 초기화
	dist[0].resize(N + 1, INF);
	dist[1].resize(N + 1, INF);

	// 각 지점 -> X로 가는 최단거리
	Dijstra(1);
	// X -> 각 지점으로 가는 최단거리
	Dijstra(0);


	int res = 0;
	for (int i = 1; i <= N; i++)
		res = max(res, dist[0][i] + dist[1][i]); // 각 지점 -> X -> 각 지점으로 가는 최단 거리들 다 구하고 최댓값 찾기

	cout << res;

	return 0;
}

 

4.  유용한 문법 및 알고리즘

4-1) 데이크스트라 알고리즘(최단거리 구하는 알고리즘)

// 데이크스트라 알고리즘(최단거리 구하는 알고리즘)
void Dijstra(int idx) {
	dist[idx][X] = 0;

	// priority_queue를 활용하여 거리가 짧은 순부터 탐색
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> q;
	q.push({ 0, X });

	while (!q.empty()) {
		int min_cost = q.top().first;
		int now = q.top().second;
		q.pop();

		// 기존의 구한 거리가 더 짧으면 넘어가기
		if (min_cost > dist[idx][now]) continue;

		// 현재 정점에서 갈 수 있는 정점 탐색
		for (int i = 0; i < graph[idx][now].size(); i++) {
			int next = graph[idx][now][i].second;
			int next_cost = min_cost + graph[idx][now][i].first;

			// 계산하여 구한 거리가 이전 거리보다 작다면, 갱신
			if (next_cost < dist[idx][next]) {
				dist[idx][next] = next_cost;
				q.push({ next_cost, next });
			}
		}
	}

}