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

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

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

#풀이

문제가 말이 어려워 이해를 잘 못했다.. 바보다 ㅋㅋㅋㅋ

 

 

맨 처음엔 최소 경로에서의 최대 비용을 출력하는 건 줄 알았다,

 

근데 신기하게도 43개 중에서 26개가 맞았다 ㅋㅋㅋ

 

근데 알고보니까 최소 경로 비용이 c이하의 경로들 중에서 최대값의 최소값을 구하는 것이었다.

 

최대의 최소를 파라미터 탐색으로 해결했던 기억이 있다,

 

c이하의 최소 경로 들중에서 최대값 lim을 정하여 lim을 넘어가면 경로로 선택하지 않았다.

 

마지막에 총 경로가 c를 넘어가면 -1을 출력하게 하였다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
#define X first
#define Y second
typedef long long ll;
ll n, m, st, en, c;
vector<pair<ll,int>> adj[100001];
ll INF = 0x3f3f3f3f3f3f3f3f;
ll hi;
int solve(ll lim){
	priority_queue < pair<ll, int>,
      vector<pair<ll, int>>,
      greater<pair<ll, int>> > pq;
	ll d[100001];
	fill(d+1,d+1+n, INF);
	d[st] = 0;
	pq.push({0, st});
	
	while(!pq.empty()){
		auto cur = pq.top(); pq.pop();
		if(cur.X != d[cur.Y]) continue;
		
		for(auto nxt: adj[cur.Y]){
			if(nxt.X > lim) continue;
			if(d[nxt.Y] <= nxt.X+d[cur.Y]) continue;
			
			d[nxt.Y] = nxt.X+d[cur.Y];
			pq.push({d[nxt.Y], nxt.Y});
		}
	
	}
	if(d[en] > c) return 0;
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >>m >> st >> en >> c;
	
	for(int i = 0; i < m; i++){
		ll a, b, w;
		cin >>a >>b >>w;
		adj[a].push_back({w,b});
		adj[b].push_back({w,a});
		hi = max(hi, w);
	}
	ll start = 0;
	while(start < hi){
		ll mid = (start+hi)/2;
		if(solve(mid)) hi = mid;
		else start = mid + 1;
	}
	
	if(solve(start)) cout << start;
	else cout << -1;
	return 0;
}