득이공간
[백준 C++] 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번
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1865 웜홀 - 벨만포드 (0) | 2024.02.02 |
---|---|
[백준 C++] 11657 타임머신 - 벨만포드 (0) | 2024.02.02 |
[백준 C++] 1005 ACM Craft - 위상정렬 (0) | 2024.02.01 |
[백준 C++] 2252 줄 세우기 - 위상정렬 (0) | 2024.02.01 |
[백준 C++] 1976 여행 가자 - 분리집합 (0) | 2024.02.01 |