[백준 28399] 황혼 (UCPC 2023 본선; Platinum IV)

 원본 그래프 G의 복사본을 만들어 각각 G1, G2라고 이름붙여줄 수 있다.

 만약 주어진 사람이 단순 경로를 처음부터 따라 이동하는 중이라면 그 사람을 G2 위로 보내고, 아니라면 G1 위로 보내자. 그러면 이것은 그냥 그래프이므로, 다익스트라를 돌리면 한 점 위에서 나머지 2n개의 정점으로 향하는 최단 경로의 길이를 구할 수 있다. 다 구한 다음에는 그래프를 다시 하나로 합쳐 주고, 정점에 부여된 가중치는 두 정점의 최솟값으로 잡으면 된다.

 

 이 문제는 체감상 다익스트라를 돌리는 과정보다 구현이 더 까다로웠다. 예를 들면, 내가 지금 주어진 단순 경로 위에 있는지, 있다면 주어진 단순 경로의 다음 정점은 몇 번인지를 어떻게 O(1)에 구하는가? 이 문제를 해결하기 위해 vector를 2개 만든다. 첫 번째 vector의 이름은 is_begin_vertex로, 주어진 vertex가 주어진 단순 경로의 시작점인지를 저장한다. 두 번째 vector의 이름은 nexts로, nexts[v]의 값은 다음과 같다.

• v가 주어진 단순 경로 위에 있다면, nexts[v]는 그 경로의 다음 정점
• v가 주어진 단순 경로 위에 있고 그 경로의 끝지점이라면, nexts[v]는 -2
• v가 어떤 단순 경로에도 포함되지 않는다면, nexts[v]는 -1

모든 정점이 많아야 하나의 단순 경로에만 포함되기 때문에 각 정점당 int 2개의 정보만 저장해도 무리가 없다.

 

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 INF = std::numeric_limits<i64>::max() / 2;

struct CellInfo {
    int v_idx, state;
    i64 val;
    
    auto operator<=>(const CellInfo& rhs) const {
        return val <=> rhs.val;
    }

    constexpr static int mem_num = 3;
};

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    
    auto graph = std::vector(n, std::vector<std::pair<int, i64>>());
    
    for (int i = 0; i < m; ++i) {
        int src, dest;
        i64 val;
        std::cin >> src >> dest >> val;
        src -= 1;
        dest -= 1;
        graph[src].emplace_back(dest, val);
    }
    
    auto lists = std::vector(k, std::vector<int>());
    for (auto& list : lists) {
        int t;
        std::cin >> t;
        
        for (int i = 0; i < t; ++i) {
            int v;
            std::cin >> v;
            v -= 1;
            
            list.push_back(v);
        }
    }
    
    std::vector is_begin_vertex(n, 0);
    for (const auto& list : lists) {
        is_begin_vertex[list[0]] = 1;
    }
    
    constexpr int END = -2, NIL = -1;
    constexpr int ON = 1, OFF = 0;
    std::vector<int> nexts(n, NIL);
    for (const auto& list : lists) {
        for (std::size_t i = 0; i < list.size() - 1; ++i) {
            nexts[list[i]] = list[i + 1];
        }
        nexts[list.back()] = END;
    }
    
    std::vector dist0(n, INF);
    auto dist1 = dist0;
    
    std::priority_queue<CellInfo, std::vector<CellInfo>, std::greater<>> pq;
    
    if (!is_begin_vertex[0]) {
        dist0[0] = 0;
        pq.push({0, OFF, 0});
    } else {
        dist1[0] = 0;
        pq.push({0, ON, 0});
    }
    
    while (!pq.empty()) {
        auto [v, state, val] = pq.top();
        pq.pop();
        
        if (state == ON && dist1[v] < val) continue;
        if (state == OFF && dist0[v] < val) continue;
        
        for (auto [next, edge_val] : graph[v]) {
            if (state == ON && nexts[v] == next && nexts[next] == END) {
                continue;
            }
            
            i64 tot_val = val + edge_val;
            int next_state = is_begin_vertex[next] || (state == ON && nexts[v] == next);
            
            if (next_state == OFF) {
                if (tot_val < dist0[next]) {
                    dist0[next] = tot_val;
                    pq.push({next, OFF, tot_val});
                }
            } else {
                if (tot_val < dist1[next]) {
                    dist1[next] = tot_val;
                    pq.push({next, ON, tot_val});
                }
            }
        }
    }
    
    for (int i = 0; i < n; ++i) {
        if (i64 ret = std::min(dist0[i], dist1[i]); ret == INF) {
            std::cout << -1 << ' ';
        } else {
            std::cout << ret << ' ';
        }
    } std::cout << "\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}

 

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

28399번: 황혼