백준1800 인터넷 설치

작성일 | In

문제 링크

  • http://icpc.me/1800

문제 출처

  • USACO 2008 January Silver 3번

사용 알고리즘

  • Dijkstra

시간복잡도

  • O(P log V log 1e6)

풀이

x원 이하의 비용으로 1번 컴퓨터와 N번 컴퓨터를 연결시킬 수 있는지 판별하는 결정 문제로 바꿔서 풀어봅시다.

x원 이하의 비용을 들이기 위해서는 x원보다 비싼 간선을 포함하지 않거나, 포함하더라도 K개 이하로 포함해야 합니다.
그러므로 x원 이하의 간선의 가중치는 0, x원보다 비싼 간선의 가중치는 1로 잡고 다익스트라를 돌려주면 됩니다.

결정 문제를 해결할 수 있으므로 최소 비용을 구하는 것은 쉽습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int, int> p;

int n, m, k;

vector<p> g[1010];
int dist[1010];

bool chk(int x){
	priority_queue<p> pq; pq.push({ 0, 1 });
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	while (pq.size()){
		int now = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (dist[now] < cost) continue;
		for (auto i : g[now]){
			int nxt = i.first;
			int nxtCost = cost + (i.second > x);
			if (nxtCost < dist[nxt]){
				dist[nxt] = nxtCost;
				pq.push({ -nxtCost, nxt });
			}
		}
	}

	return dist[n] <= k;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++){
		int s, e, x; cin >> s >> e >> x;
		g[s].push_back({ e, x });
		g[e].push_back({ s, x });
	}

	int ans = -1;
	int l = 0, r = 1e7;
	while (l <= r){
		int mid = l + r >> 1;
		if (chk(mid)){
			ans = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	cout << ans;
}