[C++] 백준 1800번 : 인터넷설치

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

1800번: 인터넷 설치

 

1. 접근

다익스트라 + 경로저장으로 풀 수 있을 줄 알았다.

하지만 구하려는 값이 최단 경로의 최소비용이 아닌 모든 경우의 최소비용이기 때문에 틀린 방식이었다.

 

2. 풀이

결국 검색으로 힌트를 얻고 풀 수 있었다

이분 탐색 + 다익스트라로 푸는 것인데, 이분 탐색으로 비용 상한선을 설정한 뒤, 다익스트라에 적용한다

이 때, K개 연결에 대해서는 무료인 조건을 활용하기 위해

d[n]에 일반적으로 저장했던 누적비용이 아닌, 비용 상한선이 넘는 값을 카운트 해준다. 이걸 구현하는게 포인트

최소비용 값은 이분 탐색 시 사용하는 중간값(m)으로 기록 가능하기에 가능하다

 

나중에 한번 더 풀어봐야할 문제

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct comp {
	bool operator()(pair<int,int> a, pair<int,int> b) {
		return a.second > b.second;
	}
};

int N, P, K;
int a, b, c;
int s, e, m;
vector<vector<pair<int, int>>> v;
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
int d[1001];
int res = -1;


bool dijkstra(int upper) {	
	for (int i = 1; i <= N; i++)
		d[i] = INT_MAX;

	pq.push({ 1,0 });
	d[1] = 0;

	while (!pq.empty()) {
		int src = pq.top().first, cost = pq.top().second;
		pq.pop();

		if (d[src] < cost)
			continue;

		for (int i = 0; i < v[src].size(); i++) {
			int dest = v[src][i].first, totCost = cost + (v[src][i].second > upper); // 비용상한선을 넘는다면 카운팅

			if (d[dest] > totCost) {
				d[dest] = totCost;
				pq.push({ dest, totCost });
			}
		}
	}

	return d[N] <= K;
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> P >> K;

	v.resize(N + 1);
	s = 0, e = P - 1;

	for (int i = 0; i < P; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });

		e = max(e, c);
	}
	
	while (s <= e) {
		m = (s + e) / 2;
		if (dijkstra(m)) {
			res = m;
			e = m - 1;
		}
		else {
			s = m + 1;
		}
	}


	cout << res;

	return 0;
}