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

1238번: 파티

cpp

#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번