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

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

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

이분 탐색을 통해 특정 비용 이하의 도로만 이용하면서 현재 가진 돈을 가지고 목적지까지 이동할 수 있는지 확인하는 방법으로 문제를 해결했다. 이때 가진돈을 가지고 목적지까지 갈 수 있는지 판단하는 방법은 다익스트라를 이용했다. 즉 다익스트라를 이용해 이동하면서 특정 비용 이하의 도로만 이동할 수 있도록 제한했다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;

int n, m;
int a, b;
long long c;
vector<pair<long long, int>> adj[100005];

//max_cost : 이동할 수 있는 도로의 최고 비용
bool Solve(int start, int dest, long long max_cost)
{
	vector<long long> short_cost(100005, numeric_limits<long long>::max());
	priority_queue<pair<long long, int>> pq;

	short_cost[start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty()) {

		int here = pq.top().second;
		long long here_cost = -pq.top().first;
		pq.pop();

		if (here_cost > short_cost[here])
			continue;

		//도착점에 도착했을때
		if (here == dest)
			return true;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].second;
			long long there_cost = here_cost + adj[here][i].first;

			//해당 도로를 지날 수 없을때
			if (adj[here][i].first > max_cost)
				continue;

			//가진 돈을 초과할때
			if (there_cost > c)
				continue;

			if (short_cost[there] > there_cost)
			{
				short_cost[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}

		}
	}

	return false;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> a >> b >> c;

	for (int i = 0; i < m; i++) {
		int u, v;
		long long cost;
		cin >> u >> v >> cost;

		adj[u].push_back(make_pair(cost, v));
		adj[v].push_back(make_pair(cost, u));
	}

	long long left = 1;
	long long right = 1000000000;
	long long result = -1;
	long long mid;

	while (left <= right) {

		mid = (left + right) / 2;

		if (Solve(a, b, mid))
		{
			result = mid;
			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	cout << result;

	return 0;
}