백준 23840 - 두 단계 최단 경로 4 (C++)

문제

• 문제 링크

  
   BOJ 23840 - 두 단계 최단 경로 4 
  

• 문제 요약

$N$개의 정점으로 이루어진 그래프와 $P$개의 중간 정점이 주어진다.
출발 정점에서 $P$개의 중간 정점 모두를 거친 후 도착 정점에 도달하는 최단 거리를 구해보자.

• 제한

TL : $7$ sec, ML : $1024$ MB




$10 ≤ N ≤ 100,000$

$10 ≤ M ≤ 300,000$

$1 ≤ w ≤ 1,000,000$

$3 ≤ P ≤ min(20, N - 3)$

알고리즘 분류

• 그래프 이론(graphs)
• 다익스트라(dijkstra)
• 다이나믹 프로그래밍(dp)
• 비트필드를 이용한 다이나믹 프로그래밍(dp_bitfield)
• 비트마스킹(bitmask)
• 외판원 순회 문제(tsp)

풀이

출발 정점으로부터 $P$개의 정점을 모두 거친 후 도착 정점까지의 최단 거리를 구해야 한다.
$3 ≤ P ≤ min(20, N - 3)$ 이므로, $BitDP$를 이용한 $TSP$로 풀어볼 수 있을 듯 하다.

이를 위해선 모든 $P_i$에 대하여 다른 지점 까지의 이동 거리를 전처리 해 놓아야 한다.
구체적으로,

$W[i][j]$ : 정점 $P_i$에서 정점 $j$까지 도달 하는 최단 거리.

라 할 때, 최대 다익 $20$번으로 모든 테이블을 채워 넣을 수 있다.
이 부분에선 넉넉한 시간 제한과 자신의 코드를 믿자.

---

이제 최소 순회를 찾아내는 일만 남았다.
여기선 별로 어려울 것 없이 기본 $TSP$를 짜주면 되겠다.

$dp[i][j]$ : 마지막으로 정점 $P_i$를 방문 하였고 지금까지 방문한 정점의 상태가 $j$일 때 남은 순회 비용.

기저 사례로, 모든 $P_i$들을 순회 했다면 마지막으로 서 있던 정점에서 도착 정점으로 이동하는 비용이 발생 해야 하므로 이 거리를 리턴해 주면 된다.

반대로 처음 시작할 땐 시작점에서 임의의 $P_i$로 이동하는 비용이 발생 하므로 답은

$min(W[P_i][s] +$ $tsp$ _ $start(P_i))$ 의 값이 되겠다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 100001
using namespace std;
 
vector <pair<int, int>> Gr[N];
ll W[20][N], dp[20][1 << 20];
int n, m, s, e, P[20];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    fill(&W[0][0], &W[19][N], 1e18);
    memset(dp, -1, sizeof dp);
    cin >> n >> m;
    for (int p, q, w; m--;)
        cin >> p >> q >> w, Gr[p].emplace_back(q, w), Gr[q].emplace_back(p, w);
    cin >> s >> e >> m;
}
void Dijkstra(int x, int y)
{
    priority_queue <pair<ll, int>> Q; Q.push({ 0, y });
    for (W[x][y] = 0; Q.size();)
    {
        auto [a, b](Q.top()); Q.pop();
        if (W[x][b] >= -a)
            for (auto& [p, q] : Gr[b])
                if (ll d = q - a; d < W[x][p])
                    W[x][p] = d, Q.push({ -d, p });
    }
}
ll TSP(int p, int q)
{
    if (q == (1 << m) - 1) return W[p][e];
    ll& t(dp[p][q]), i{};
    if (!~t)
        for (t = 1e18; i < m; i++)
            if (!(q & (1 << i)))
                t = min(t, TSP(i, q | (1 << i)) + W[p][P[i]]);
    return t;
}
void Solve(ll r = 1e18)
{
    for (int i{}; i < m; i++) cin >> P[i], Dijkstra(i, P[i]);
    for (int i{}; i < m; i++) r = min(r, TSP(i, 1 << i) + W[i][s]);
    cout << (r < 1e18 ? r : -1);
}
int main()
{
    Init();
    Solve();
}

comment

끝