【AtCoder】ABC 395 E - Flip Edge | 緑コーダーが解くAtCoder

atcoder.jp

配点: 425 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 978

問題概要

頂点 辺の有向グラフが与えられ、 番目の辺は頂点 から頂点 への有向辺である。

これから、以下の操作のいずれかを繰り返し行うことで、頂点 から頂点 にたどり着くことを目指す。

• 今いる頂点から辺をたどって移動する。コストが かかる。
• すべての辺の向きを反転する。コストが かかる。

頂点 に到達するまでにかかるコストの総和の最小値を求めよ。

制約

• 
• 
• 
• 
• 与えられるグラフにおいて、上記の操作を繰り返して頂点 から頂点 にたどり着くことができる。
• 入力はすべて整数。

考察

「全ての辺の向きを反転する」という操作がなければ、ただの単一始点最短経路問題になる。

そこで、全ての辺の向きを反転したグラフと元のグラフとをコスト で行き来できると考えることにしよう。

ドラクエ6の「上の世界」と「下の世界」みたいな感じ？

この下で、頂点 から頂点 および頂点 への単一始点最短経路問題を解けばよい。

今回はオーソドックスに、 Dijkstra 法を用いてやれば良いだろう。

上図の頂点 は頂点 とすることで、長さ の隣接リストでグラフを扱える。

答えは、頂点 までの経路長と頂点 までの経路長との最小値とすればよい。

実装例では 0-indexed となっていることに注意。

実装例

#include <bits/stdc++.h>
using namespace std;

constexpr long long INFL = 1e+18;

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

using Pair = pair<ll, int>;

struct Edge
{
    int to;
    int cost;
};

int main()
{
    int N, M, X;
    cin >> N >> M >> X;
    Graph<Edge> G(2 * N);
    rep(i, 0, M)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back({v, 1});
        G[v + N].push_back({u + N, 1});
    }
    rep(i, 0, N)
    {
        G[i].push_back({i + N, X});
        G[i + N].push_back({i, X});
    }

    vector<ll> dist(2 * N, INFL);
    priority_queue<Pair, vector<Pair>, greater<Pair>> que;

    dist[0] = 0;
    que.push({0, 0});
    while (!que.empty())
    {
        auto [distance, v] = que.top();
        que.pop();

        if (dist[v] < distance)
            continue;

        for (auto edge : G[v])
        {
            if (chmin(dist[edge.to], dist[v] + edge.cost))
            {
                que.push({dist[edge.to], edge.to});
            }
        }
    }

    cout << min(dist[N - 1], dist[2 * N - 1]) << endl;

    return 0;
}

atcoder.jp

実装時間: 30分

コメント

この問題では、いわゆる「拡張ダイクストラ」という解法を用いることになったわけだが、記事内では敢えてこの単語を使わなかった。

それは、実装の上で Dijkstra 法のアルゴリズム自体は何ら拡張されていないからである。拡張したのはあくまで「探索対象のグラフ」である(今回の拡張方法は頂点倍加とも言われる)。

したがって、

• (何らかの方法で元のグラフから)拡張(されたグラフ上での)ダイクストラ法(の適用)

というのが正しい解釈だと私は考える。

「じゃあ拡張ダイクストラのことをなんていえばいいの？」っていう人がいると思うけど、そもそも「グラフを拡張してダイクストラ」を１アルゴリズムとして見ているのがおかしいので、「グラフの頂点倍加」と「ダイクストラ」を分けて言うのが正しいと思います。

— chokudai(高橋 直大)@AtCoder (@chokudai) 2020年4月30日