백준 - 1238번 : 파티 (C++)

풀이 방법 : 다익스트라

각 마을에서 X까지 걸리는 최단 시간을 탐색하는 데 입력된 그래프 정보대로만 탐색한다면 최대 1000번의 탐색이 필요할 수 있다. 이를 방지하기 위해 입력된 그래프 정보를 반대로 저장하여 역방향 그래프를 하나 만들어내고 그를 통해 X에서 각 마을까지 가는데 걸리는 시간을 구하면 결국 각 마을에서 X까지 가는데 걸리는 시간을 한 번에 구해낼 수 있다.
그렇게되면 순방향 그래프에서 탐색, 역방향 그래프에서 탐색 총 두 번의 탐색으로 문제를 해결할 수 있다.

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

using namespace std;

struct PosInfo
{
	int Pos = 0;
	int Time = 0;
};

struct Road
{
	int Dest = 0;
	int Time = 0;
};

struct cmp
{
	bool operator() (const PosInfo& Src, const PosInfo& Dest)
	{
		return Src.Time > Dest.Time;
	}
};

void Dj(int Start, const vector<vector<Road>>& Graph, vector<int>& vecDist)
{
	priority_queue<PosInfo, vector<PosInfo>, cmp> pqPos;
	PosInfo Info;
	Info.Pos = Start;
	Info.Time = 0;

	pqPos.push(Info);

	while (!pqPos.empty())
	{
		PosInfo Current = pqPos.top();
		pqPos.pop();

		int Size = Graph[Current.Pos].size();

		for (int i = 0; i < Size; ++i)
		{
			PosInfo Next = Current;
			Next.Pos = Graph[Current.Pos][i].Dest;
			Next.Time += Graph[Current.Pos][i].Time;

			if (vecDist[Next.Pos] == 0)
			{
				vecDist[Next.Pos] = Next.Time;
				pqPos.push(Next);
			}

			else
			{
				if (Next.Time < vecDist[Next.Pos])
				{
					vecDist[Next.Pos] = Next.Time;
					pqPos.push(Next);
				}

			}

		}
	}
}

int main()
{
	int N, M, X;

	cin >> N >> M >> X;

	vector<vector<Road>> Graph(N + 1);
	vector<vector<Road>> RevGraph(N + 1);

	for (int i = 0; i < M; ++i)
	{
		int Start, Dest, Time;

		cin >> Start >> Dest >> Time;

		Road R;
		R.Dest = Dest;
		R.Time = Time;
		
		Graph[Start].push_back(R);

		R.Dest = Start;
		RevGraph[Dest].push_back(R);
	}

	vector<int> vecDist(N + 1);
	vector<int> vecRevDist(N + 1);

	Dj(X, RevGraph, vecRevDist);

	Dj(X, Graph, vecDist);

	int Max = 0;

	vecDist[X] = 0;
	vecRevDist[X] = 0;

	for (int i = 1; i <= N; ++i)
	{
		Max = max(Max, vecDist[i] + vecRevDist[i]);
	}

	cout << Max;

}