[백준] 1800번: 인터넷 설치 C++ - 다익스트라가 메인 로직이 아닐 수 있다. 결정 문제의 비밀을 알려드립니다. 💀💀☠️☠️😎

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

 

문제를 분석해보면

1. 다익스트라로 1->N까지의 경로는 구할 수 있다.

2. 하지만 그 경로가 정답인지 확정할 수 없다.

3. 문제는 "최대 비용을 최소화" 하라는 최적화 문제이다.

 

최적화 문제의 변수를 "mid"라 하자. 답을 저장할 변수를 mid라 하는 것이다.

원래의 문제는 1->N 경로 중 최대 요금이 가장 작은 mid를 찾는 것이다.

이를 결정 문제로 변경하면 1->N 경로 중 최대 요금을 mid 이하로 만들 수 있을까? 가 된다.

1. mid로 경로를 경로를 만들었는데 해당 경로의 요금이 mid 초과인 수를 셌을 때 K 초과라면?
   • mid로는 답을 낼 수 없다. 현재 mid 보다 더 큰 요금을 상한선으로 잡아야 한다.
2. 반대라면 현재의 mid도 가능하고 더 적어도 된다.
3. 현재의 mid로 경로를 구할 때 다익스트라를 변경하면 된다. 요금이 mid 이상이면 weight를 1, 아니라면 0으로 두는 것이다. 그리고 다익스트라를 때려서 최종 경로의 weight가 K 초과인지만 판단하면 된다.

 

마지막으로 파라미터릭 서치를 적용해도 되는 것인지 단조성을 증명해보자.

• 최대 요금이 100원 일 때 연결이 된다면 101원도 가능하다.
• 100원 일 때 불가능하다면 49원은 불가능하다.
• 단조성이 증명되었다!

/**  **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int n, p, k, ans = -1;
vector<pair<int, int>> adj[1002];

int func(int mid)
{
    // mid보다 크면 weight를 1로 생각
    vector<int> dist(n + 1, 0x7f7f7f7f);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

    while (!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();

        // dist[cur.second]와 우선순위 큐의 정점이 다른 경우
        if (dist[cur.second] < cur.first)
            continue;
        for (auto nxt : adj[cur.second])
        {
            int nxt_cost = cur.first + (nxt.first > mid);
            if (dist[nxt.second] > nxt_cost)
            {
                // 갱신
                dist[nxt.second] = nxt_cost;
                pq.push({nxt_cost, nxt.second});
            }
        }
    }

    return dist[n];
}

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

    cin >> n >> p >> k;
    for (int i = 0; i < p; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }

    int left = 0, right = 1000000;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (func(mid) <= k)
        {
            ans = mid;
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }

    cout << ans;
}

/*
1~N번 연결
K개의 선은 공짜
나머지 선 중 가장 비싼 것을 구하기.

다익스트라 -> ElogE. E=10000
K개의 선이 공짜라서 단순 다익스트라로는 불가능함.

결정 문제로 바꿔서 남은 것 중 최대 비용을 mid로 한다면 연결이 가능한가?를 보면 된다.
1~n까지를 연결해서 mid 초과인 간선을 셌을 때 K 이상이라면?
-> mid는 현재보다 크다.
아니라면 mid는 현재보다 작다.

경로를 구하는 것은. 케이블 비용이 mid 보다 크다면 가중치를 1로 두고, 아니라면 0으로 둬서 다익스트라로 구할 수 있다.

*/