[백준 C++] 1238 파티 - 다익스트라

1238번: 파티

#include <iostream>
#include <climits>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;

const int& Infinite = INT_MAX;

vector<list<pair<int, int>>> Neighbors;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> SearchQueue;
vector<int> Solution;

vector<int> Dijkstra(int N, int Start)
{
	vector<int> Times;
	Times.reserve(N);

	for (int i = 0; i < N; ++i)
	{
		Times.emplace_back(Infinite);
	}
	Times[Start] = 0;

	SearchQueue.emplace(0, Start);
	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.top().second;
		int CurrentTime = SearchQueue.top().first;
		SearchQueue.pop();

		if (CurrentTime > Times[Current])
		{
			continue;
		}

		for (const pair<int, int>& Neighbor : Neighbors[Current])
		{
			int NewTime = Times[Current] + Neighbor.first;
			if (NewTime < Times[Neighbor.second])
			{
				Times[Neighbor.second] = NewTime;
				SearchQueue.emplace(NewTime, Neighbor.second);
			}
		}
	}

	return Times;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, X;
	cin >> N >> M >> X;

	Neighbors.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Neighbors.emplace_back(list<pair<int, int>>());
	}

	for (int i = 0; i < M; ++i)
	{
		int Start, End, Weight;
		cin >> Start >> End >> Weight;

		Neighbors[Start - 1].emplace_back(Weight, End - 1);
	}

	vector<int> ReturnTimes = Dijkstra(N, X - 1);

	Solution.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		vector<int> GoingTimes = Dijkstra(N, i);
		int TotalTime = GoingTimes[X - 1] + ReturnTimes[i];
		Solution.emplace_back(TotalTime);
	}

	cout << *max_element(Solution.begin(), Solution.end());
}

---

최단 거리 탐색 문제로 다익스트라 알고리즘을 이용했습니다.

모든 노드의 정보(X 노드로 갈 때의 최단 거리 + X 노드에서 돌아올 때의 최단 거리)를 구해준 다음

그 중 최대값을 출력하도록 구현했습니다.

 

각 노드 마다 최단 거리를 계산해야하기 때문에 다익스트라 알고리즘이 여러번 수행됩니다.

X 노드로 갈 때의 최단 거리: 다익스트라 알고리즘 N번

X 노드에서 돌아올 때의 최단 거리: 다익스트라 알고리즘 1번