[백준][1238] 파티

이 포스트는 백준 사이트의 파티 문제 풀이입니다.

문제

해결 과정

이 문제는 다익스트라 알고리즘을 활용해서 해결할 수 있습니다.

입력받은 정보를 토대로 단방향 가중치 그래프를 만든 후
(현재 마을에서 X까지 비용) + (X부터 원래 마을까지 비용)을 매번 비교하여 최댓값을 구하면 됩니다.

일반적인 다익스트라의 경우, 최단 거리를 구하기 위해서 우선순위 큐의 내부 구현체인 최대힙에
값을 넣기 전 음수 부호를 붙이지만

이 문제의 경우, 최대 비용을 구하는 문제이므로
부호 없이 그대로 최대힙을 이용하여 문제를 해결할 수 있습니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M, X;
vector<vector<pair<int, int>>> adj_list;

int get_cost(int start_node, int end_node);


int main() {
	cin >> N >> M >> X;
	adj_list.assign(M + 1, vector<pair<int, int>>());
	
	int start_node, end_node, cost;
	for (int i = 0; i < M; ++i) {
		cin >> start_node >> end_node >> cost;
		adj_list[start_node].push_back({ end_node, cost });
	}

	int max_cost = 0;
	for (int i = 1; i <= N; ++i) {
		int new_cost = get_cost(X, i) + get_cost(i, X);
		max_cost = max(new_cost, max_cost);
	}

	cout << max_cost;

	return 0;
}


int get_cost(int start_node, int end_node) {
	vector<int> dist(M + 1, -1);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, start_node });

	while (false == pq.empty()) {
		int cur_dist = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		if (dist[cur_node] != -1) 
            continue;

		dist[cur_node] = cur_dist;

		for (auto& adj_node : adj_list[cur_node]) {
			if (dist[adj_node.first] != -1) 
                continue;

			pq.push({ cur_dist + adj_node.second, adj_node.first });
		}
	}

	return dist[end_node];
}

실행 결과