문제요약

$N(2 \leq N \leq 15)$명의 사람이 $1$번 구역에서 $2$번 구역으로 이동해야한다.

각 사람에게는 이동시간 $t_i(1 \leq t_i \leq 5000)$가 부여되어있다.

이동하기 위해서는 투명망토를 사용해야 하는데, 투명망토는 한 번에 $2$명씩만 사용할 수 있다. $i$번 사람, $j$번 사람이 이용하였다 했을 때, 이 때 비용은 $max(t_i,\ t_j)$이다. 모든 사람이 $2$번 구역으로 이동하도록 하는 최소 비용을 구하여라. 처음에 모든 사람은 $1$번 구역에 있다.

풀이

상태공간을 다음과 같이 정의하자.

$dist(state, flg) =$ 사람들의 현재 위치가 $state$상태이고 $flg = 0$이면 투명망토가 $1$번 구역에, $flg = 1$이면 투명망토가 $2$번 구역에 있을 때 $state = 0$으로부터의 최단거리. 이 때 $state$는 $2$진수로 $i$번째 비트는 $i$번 사람이 $1$번구역에 있다면 $0$, $2$번 구역에 있다면 $1$이다.

상태공간의 크기는 $state$가 $2^{15}$, $flg$가 $2$이므로, 총 $2^{16} \approx 64000$정도이다. 이 때 하나의 상테에서 전이 되는 수는 최대 $_{15}C_2 + 15 \approx 100$개이다. 따라서 정점의 크기가 $N = 2^{16}$, 간선의 크기가 약 $E \approx 2^{16} \times 100$정도인 그래프로 모델링 할 수 있다. 따라서 이 문제는 시간복잡도가 $\mathcal O(ElogV)$인 다익스트라 알고리즘으로 해결할 수 있다.

정답코드

#include <bits/stdc++.h>
#define ll long long
//#define int long long
const int inf = 1e9;

using namespace std;
typedef array<int, 3> arr;

int n;
int dist[(1 << 15)][2];
vector<int> a;

void dijkstra(int start){
    for (int i = 0; i < (1 << n); i++) dist[i][0] = dist[i][1] = inf;
    dist[start][0] = 0;
    priority_queue<arr, vector<arr>, greater<>> pq;
    pq.push({0, start, 0});

    while (!pq.empty()){
        auto [dis, now, flg] = pq.top(); pq.pop();

        if (dis > dist[now][flg]) continue;

        if (!flg){
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n && j != i; j++){
                    int msk1 = (1 << i);
                    int msk2 = (1 << j);
                    if (!(now&msk1) && !(now&msk2)){
                        int next = now | msk1 | msk2;
                        int cost = dist[now][flg] + max(a[i], a[j]);
                        if (cost < dist[next][flg^1]){
                            dist[next][flg^1] = cost;
                            pq.push({cost, next, flg^1});
                        }
                    }
                }
            }
        } else {
            for (int i = 0; i < n; i++){
                int msk1 = (1 << i);
                if (now&msk1){
                    int next = now^msk1;
                    int cost = dist[now][flg] + a[i];
                    if (cost < dist[next][flg^1]){
                        dist[next][flg^1] = cost;
                        pq.push({cost, next, flg^1});
                    }
                }
            }
        }
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++){
        int x; cin >> x;
        a.push_back(x);
    }

    dijkstra(0);

    cout << dist[(1 << n)-1][1];
    
    return 0;
}