006 - Min-Max Propagation　解説

解説

　この問題は、目的の値 $Y$ が配列内で連続して存在する区間 $[l, r]$（初期状態は $[Y, Y]$）をどのように広げていくかという問題に言い換えることができます。目標は、この区間が $X$ を包含する（すなわち $X < Y$ なら $l \le X$、$X > Y$ なら $r \ge X$ を満たす）ための最小コストを求めることです。

　魔法の操作が区間 $[l, r]$ に与える影響を考えます。魔法 $0$（最小値で置き換え）を行う場合、区間内に $Y$ より小さい値（初期状態では $Y$ より左側にある要素）が含まれると、$Y$ が消滅してしまいます。また、$Y$ 自身が含まれていないと $Y$ を広げられません。したがって、魔法 $i$ ($T_i = 0$) が有効であるための条件は $l \le L_i \le r$ であり、これを使うと区間の右端を $r = \max(r, R_i)$ に拡張できます。 同様に、魔法 $i$ ($T_i = 1$) が有効であるための条件は $l \le R_i \le r$ であり、これを使うと区間の左端を $l = \min(l, L_i)$ に拡張できます。

　ここで重要な性質として、初期状態から常に $l \le Y \le r$ が成り立っているため、「$x \ge Y$ に対して $l \le x$ は常に真」「$x \le Y$ に対して $r \ge x$ は常に真」となります。つまり、左端 $l$ の拡張と右端 $r$ の拡張の条件は、 $Y$ を境に完全に独立して扱うことができます。これにより、各座標 $x (1 \le x \le N)$ について「$x \ge Y$ なら $r \ge x$ を達成した状態」「$x \le Y$ なら $l \le x$ を達成した状態」を表す $N$ 頂点のグラフの最短経路問題に帰着できます。

　具体的には、頂点 $1$ から $N$ を持つ有向グラフを考え、頂点 $Y$ を始点としてダイクストラ法を行います。辺の張り方は以下の通りです。

• 広い範囲を達成できれば狭い範囲も達成できるため、コスト $0$ の辺を $x > Y$ には $x \to x-1$、$x < Y$ には $x \to x+1$ に張る。
• 魔法 $T_i = 0$ は、条件 $L_i$ を満たせば $R_i$ まで右端が伸びるため、頂点 $L_i$ から頂点 $\max(Y, R_i)$ へコスト $C_i$ の辺を張る。
• 魔法 $T_i = 1$ は、条件 $R_i$ を満たせば $L_i$ まで左端が伸びるため、頂点 $R_i$ から頂点 $\min(Y, L_i)$ へコスト $C_i$ の辺を張る。

構築したグラフ上で、頂点 $Y$ から頂点 $X$ への最短経路を求めれば答えとなります。頂点数・辺数ともに $O(N + M)$ であるため、計算量は $O((N + M) \log N)$ となり十分高速です。

コード例

以下はC++による想定解法のコードです。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 2e18;

struct Edge {
    int to;
    long long cost;
};

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, X, Y;
    if (!(cin >> N >> M >> X >> Y)) return 0;
    
    vector<vector<Edge>> G(N + 1);
    
    // コスト0の辺（包含関係による伝播）
    for (int i = Y + 1; i <= N; ++i) {
        G[i].push_back({i - 1, 0});
    }
    for (int i = Y - 1; i >= 1; --i) {
        G[i].push_back({i + 1, 0});
    }
    
    // 魔法に対応する辺
    for (int i = 0; i < M; ++i) {
        int T, L, R;
        long long C;
        cin >> T >> L >> R >> C;
        
        if (T == 0) {
            // T = 0 : 区間の右端を拡張
            G[L].push_back({max(Y, R), C});
        } else {
            // T = 1 : 区間の左端を拡張
            G[R].push_back({min(Y, L), C});
        }
    }
    
    // ダイクストラ法
    vector<long long> dist(N + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    
    dist[Y] = 0;
    pq.push({0, Y});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        if (u == X) break; // 目的の頂点に到達したら終了
        
        for (const auto& edge : G[u]) {
            if (dist[edge.to] > dist[u] + edge.cost) {
                dist[edge.to] = dist[u] + edge.cost;
                pq.push({dist[edge.to], edge.to});
            }
        }
    }
    
    // 結果の出力
    if (dist[X] == INF) {
        cout << -1 << "\n";
    } else {
        cout << dist[X] << "\n";
    }
    
    return 0;
}