백준 - 11085번 : 군사 이동 (C++)

풀이 방법 : 다익스트라(?)

사실 다익스트라 말고 MST처럼 푸는게 더 빠를듯 근데 자신없어서 그냥 다익스트라로 풀긴 했다...
각 지점까지 도달하는 루트에서의 길의 너비의 최솟값들을 갱신해나가면서 탐색을 한다. 만약 해당 지점까지의 너비의 최솟값보다 더 작은 루트일경우 탐색을 취소하는 식으로 진행해주고, 목표지점에 도달할 때까지 이를 반복해주면 된다.

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

using namespace std;

int Graph[1001][1001] = {};
int DPWidth[1001] = {};

struct Route
{
	int Current = -1;
	int MinWidth = 1001;
};

struct cmp
{
	bool operator() (const Route& Src, const Route& Dest)
	{
		return Src.MinWidth < Dest.MinWidth;
	}
};

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

	int p, w;
	cin >> p >> w;
	int c, v;
	cin >> c >> v;

	for (int i = 0; i < w; ++i)
	{
		int Start, End, Width;
		cin >> Start >> End >> Width;
		Graph[Start][End] = max(Width, Graph[Start][End]);
		Graph[End][Start] = max(Width, Graph[End][Start]);
	}

	priority_queue<Route, vector<Route>, cmp> pqRoute;

	Route StartRoute;
	StartRoute.Current = c;
	pqRoute.push(StartRoute);

	int MaxOfMin = 0;

	while (!pqRoute.empty())
	{
		Route CurPos = pqRoute.top();
		pqRoute.pop();

		if (CurPos.Current == v)
		{
			MaxOfMin = max(MaxOfMin, CurPos.MinWidth);
			continue;
		}

		for (int i = 0; i < p; ++i)
		{
			if (i == CurPos.Current)
				continue;

			int NextWidth = min(CurPos.MinWidth, Graph[CurPos.Current][i]);

			if (DPWidth[i] >= NextWidth)
				continue;

			DPWidth[i] = max(DPWidth[i], NextWidth);

			Route NextPos;
			NextPos.Current = i;
			NextPos.MinWidth = NextWidth;
			pqRoute.push(NextPos);
		}
	}

	cout << MaxOfMin;
}