[ boj : 20168,20182,20183 ] 골목 대장 호석 - 기능성,효율성1,효율성2

www.acmicpc.net/problem/20183

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

문제 : (그냥 20183 하나만 링크하겠습니다.) 호석이는 A->B로 이동하고 싶어합니다. 이때 각 간선마다 가중치가 주어지고 A->B까지 도착하는데 방문한 간선 중 최대값을 도출하는데 B까지 도착했을때 도출된 "최대값들의 최소값"을 구하는게 문제입니다.

 

해설 : 그냥 단순한 '다익스트라'문제인 줄 알고 덤볐다가 ??????되었던 문제입니다.

이 문제는 '전형적인' 문제에 속하니 처음 풀어보셨거나 접해본 분들은 깊이 습득하시길 바라겠습니다.

 

먼저 각 정점을 A->B로 가면서 간선마다 매번 갱신해가며 답을 도출하기엔 어려움이 있습니다. 또한, 다익스트라를 사용해 가며 답을 갱신시키는 것 또한 다익스트라가 가지고 있는 성질에 위배되는 행위를 하기 때문에 적절치 못한 방법이죠.

 

그러면 어떻게 해결해야 될까요?

우린 결국에는 이 문제에 답은 주어진 제한조건의 범위 내에 있다는 것을 알 수 있습니다.

무슨 말이냐면 

 

• 1<= 골목 별 수금액<=20
• 1 ≤ 골목 별 수금액 ≤ 10^9

이 조건내에 답이 있다는 것이죠. 결국 주어진 간선의 가중치 중 하나가 답일 테니까요.

그러면 단순하게 1부터 20,10^9까지 전부 확인해보면 되겠죠. 이 중 답이 있을테니까요. 그 다음에 다익스트라 알고리즘을 적용시켜 A->B까지 갈 수 있는지 없는지를 확인해 보면 됩니다.

bfs는 사용하면 안되는 것 인가요???안돼죠 같은 정점사이끼리 다수의 간선이 주어질 수도 있고 n과 m의 범위가 결코 제한시간안에 들어가지 못하니까요.

 

효율성1 같은 경우는 그냥 1~20까지 for문을 돌려 확인하면 됩니다. 그러나 효율성2 같은 경우는 불가능하죠 범위때문에 시간초과에 걸릴 테니까요.

그래서 파라메트릭 서치를 이용하는 것 입니다. 이때 주의해야 할점은 범위가 int형을 넘긴다는 것과 이분 탐색시 r의 범위 설정시 C의 범위를 넘겨 설정해야된다는 점 입니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct info {
	ll to, weight;
	bool operator<(const info& cur) const {
		return weight > cur.weight;
	}
};

ll n, m, A, B, C;
ll dist[100001];
vector<info> v[100001];

const ll inf = (ll)1e15;
bool dijk(ll x, ll cost);

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

	ll x, y,c;
	cin >> n >> m >> A >> B >> C;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> c;
		v[x].push_back({ y,c });
		v[y].push_back({ x,c });
	}
	ll ans = -1;
	ll l = 0, r = inf;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (!dijk(A,mid))
			l=mid+1;
		else {
			ans = mid;
			r = mid - 1;
		}
	}
	cout << ans;
	return 0;
}
bool dijk(ll x,ll cost)
{
	for (int i = 1; i <= n; i++) 
		dist[i] = inf;
	
	priority_queue<info> pq;
	pq.push({ x,0 });
	dist[x] = 0;
	while (!pq.empty())
	{
		info cur = pq.top();
		pq.pop();

		if (dist[cur.to]<cur.weight)continue;

		for (int i = 0; i < v[cur.to].size(); i++) {
			ll next = v[cur.to][i].to;
			ll next_weight = v[cur.to][i].weight;
			if (cost>=next_weight && dist[next] > dist[cur.to] + next_weight) {
				dist[next] = dist[cur.to] + next_weight;
				pq.push({ next,dist[next] });
			}
		}
	}
	if (dist[B] <= C)return true;
	return false;
}