취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1800번 문제인 인터넷 설치이다.
문제는 아래 링크를 확인하자.

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

문제를 다른 시각으로 해석해보자. 1번 컴퓨터와 $N$번 컴퓨터를 이을 수 있다는 전제 하에, 주어진 문제는 "어떤 $x$에 대하여 비용 $x$를 넘는 에지를 $K$개 이하로 사용해 1번 컴퓨터와 $N$번 컴퓨터 사이를 이을 수 있는 최소 $x$는 무엇인지"를 찾는 문제로 생각할 수 있다. 어떤 $x$값에 대하여 두 컴퓨터를 이을 수 있다면 그보다 큰 $x$값이 주어져도 두 컴퓨터를 이을 수 있으며 두 컴퓨터를 이을 수 없다면 그보다 작은 $x$값이 주어져도 두 컴퓨터를 이을 수 없으므로, $x$의 값은 이진탐색을 이용해 계산할 수 있다.

두 컴퓨터가 이어질 수 있는지를 생각해야 한다는 점을 잊지 말자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

int N, E, K;
vector<pair<int, int>> G[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int dist[1001];
bool dijkstra(int mid) {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
        int cur = pq.top().second, d = pq.top().first; pq.pop();
        if (dist[cur] < d) continue;
        for (auto &p:G[cur]) {
            int nxt = p.first, dd = d;
            if (p.second > mid) dd++;
            if (dd < dist[nxt]) dist[nxt] = dd, pq.push(make_pair(dd, nxt));
        }
    }
    return (dist[N] <= K);
}

int L, R = 1000001;

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

    cin >> N >> E >> K;
    while (E--) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(make_pair(y, w));
        G[y].emplace_back(make_pair(x, w));
    }

    while (L < R) {
        int mid = (L + R) / 2;
        if (dijkstra(mid)) R = mid;
        else L = mid + 1;
    }
    if (L == 1000001) cout << -1;
    else cout << L;
}