[백준] 20183 - 골목 대장 호석 - 효율성 2

https://www.acmicpc.net/problem/20183

20183번: 골목 대장 호석 - 효율성 2

 

int overflow와 부등호 때문에 많은 애를 먹었던 문제이다.

핵심은 파라메트릭 서치 + 다익스트라이다.

파라매트릭 서치의 매개 변수로, 지나온 경로의 최대의 최소를 정한다. 이후 각 이분 탐색마다 지정한 제한을 넘지 않게 다익스트라를 돌리면 된다.

 

이분 탐색에서 초기 left와 right는 어떻게 정해야 할까?

생각해 보면 모든 답은 -1 또는 주어진 간선의 가중치 범위에서 존재한다.

따라서 left = min(모든 간선의 가중치), right = max(모든 간선의 가중치)로 설정할 수 있다.

 

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

long long n, m, a, b, c;
long long disC[100001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> a >> b >> c;
	vector<vector<pair<long long, long long>>> v(n + 1);
	long long start = LLONG_MAX, end = 0;

	for (int i = 0; i < m; i++)
	{
		long long n1, n2, cost;
		cin >> n1 >> n2 >> cost;
		v[n1].push_back({n2, cost});
		v[n2].push_back({n1, cost});
		start = min(start, cost);
		end = max(end, cost);
	}

	long long ans = -1;

	while (start <= end)
	{
		long long mid = (start + end) / 2;
		memset(disC, -1, sizeof(disC));

		priority_queue<pair<long long, long long>> pq;
		pq.push({0, a});
		disC[a] = 0;

		while (!pq.empty())
		{
			long long node = pq.top().second, cost = -pq.top().first;
			pq.pop();

			if (disC[node] < cost)
				continue;

			for (auto &i : v[node])
			{
				long long nextNode = i.first;
				long long nextCost = i.second + cost;
				if (i.second > mid || nextCost > c || (disC[nextNode] != -1 && disC[nextNode] <= nextCost))
				{
					continue;
				}
				pq.push({-nextCost, nextNode});
				disC[nextNode] = nextCost;
			}
		}

		if (disC[b] != -1)
		{
			ans = mid;
			end = mid - 1;
		}
		else
		{
			start = mid + 1;
		}
	}
	cout << ans;
}