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

1. 문제 풀이

 문제 유형은 parametric search와 dijkstra입니다. 우선 이분 탐색으로 1번 컴퓨터에서 N번 컴퓨터를 연결하는데 최대로 사용할 수 있는 금액 cost를 결정합니다. 이후 간선의 가중치 정보를 cost에 맞추어 재가공하는데 cost보다 작거나 같다면 0으로 크다면 1로 간주하여 N번 컴퓨터까지 연결하는데 cost보다 비용이 큰 케이블의 개수가 몇 개인지 구합니다. 만약 d[n]에 저장되어 있는 값이 k보다 작거나 같다면 해당 cost로 탐색이 가능하다고 간주할 수 있습니다.

 

2. 소요 시간 및 경과

• 시작 시간: 15시 16분
• #1 제출 시간: 16시 06분
  • 67% WA
  • 원인: N번 컴퓨터를 연결 못하는 경우를 구현하지 않음
• #2 제출 시간: 16시 12분
  • 67% WA
• #3 제출 시간: 16시 13분
  • 67% WA
  • 원인: 1번 컴퓨터에서 N번 컴퓨터를 연결하는데 K번 이하의 케이블로 연결이 가능한 경우 0을 출력하지 않음
• #4 제출 시간: 16시 37분
  • AC

총 소요 시간 : 1시간 21분

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, p, k;
vpi adj[1'005];
int d[1'005];
priority_queue<pi, vpi, greater<pi>> pq;

bool dijkstra(int cost) {
    memset(d, 0x3f, sizeof(d));

    d[1] = 0;
    pq.push({0, 1});
    while(sz(pq)) {
        auto [cw, cx] = pq.top(); pq.pop();
        if(d[cx] != cw) continue;
        for(auto [nw, nx] : adj[cx]) {
            if(d[nx] > d[cx] + (nw > cost)) {
                d[nx] = d[cx] + (nw > cost);
                pq.push({d[nx], nx});
            }
        }
    }

    return d[n] <= k;
}

int main() {
    fastio(nullptr, false);

    cin >> n >> p >> k;
    while(p--) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({w, v});
        adj[v].pb({w, u});
    }

    int st{-1}, en = 1'000'001;
    while(st + 1< en) {
        int mid = (st + en) >> 1;
        (dijkstra(mid) ? en : st) = mid;
    }

    cout << (en == 1'000'001 ? -1 : en);
}

 

4. 제출 결과