AtCoder ABC 051 D - Candidates of No Shortest Paths (水色, 400 点)

「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。

問題へのリンク

より高難易度な問題の部分問題となる例として、

• RUPC 2018 day3-F 最短距離を伸ばすえびちゃん

がある。これも「最短距離として使われうる辺を挙げて、その中での s-t 最小カットを求める」というのをやる。

問題概要

頂点 辺の連結な重み付き無向単純グラフが与えられる。このグラフ上のパスであって「パスの始点と終点との間の最短路となっているもの」をすべて考えたとき、それにまったく使われることのない辺が何本あるかを求めよ。

制約

• 
• 

解法 1：僕の思考過程

この問題で要求されていることは、より高難易度な問題での重要な考察ステップの一部だったりすると思う。なので、この問題を素早く処理できることは、より高難易度な問題に挑む上で重要そう。

こういうのは、まずは自明にダメなやつをひたすら挙げて行くのが良さそう。そうしているうちにいつの間にか、すべて求められていたりする。

さて、「辺 uv がまったく使われない」ということは、uv 間の最短路が他にあることを意味する。つまり、u から v へ至る迂回路でありながら辺 uv より短い最短路というのが存在するような辺はとりあえずダメだということ。つまり、

(uv の長さ) > (u-v 間の最短路の長さ)

となっているものはダメ。次に、(uv の長さ) > (uv の最短路の長さ) となっている辺 uv をすべて取り除いてみる (この除去操作を行っても、各 2 点間の最短路は変化しないことに注意...除去しても影響のない辺のみを取り除いているので)。そうしてできたグラフでは必ず

(uv の長さ) = (u-v 間の最短路の長さ)

となることがわかる！！！！！¹

よって、残ったグラフでは uv 辺はそれ自体 u-v 間の最短路だと言えるので、すべて生き残る。こうして取り除くべき辺は

---

元のグラフで (uv 辺の長さ) > (u-v 間の最短路の長さ) となっているような辺 uv

---

であることがわかった。計算量は 。

#include <iostream>
using namespace std;
const int INF = 1<<29;
const int MAX_V = 110;
const int MAX_E = 1100;

int N, M;
int a[MAX_E], b[MAX_E], c[MAX_E]; // 各辺
int dist[MAX_V][MAX_V]; // Floyd-Warshall 用

int main() {
    cin >> N >> M;

    // Floyd-Warshall でよくやる初期化
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dist[i][j] = INF;
        }
        dist[i][i] = 0; // ここがポイント
    }

    // 入力
    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        --a[i], --b[i];
        dist[a[i]][b[i]] = c[i];
        dist[b[i]][a[i]] = c[i];
    }

    // Floyd-Warshall
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    // 集計
    int res = 0;
    for (int i = 0; i < M; ++i) {
        if (c[i] > dist[a[i]][b[i]]) ++res;
    }
    cout << res << endl;
}

解法 2: もっと思考停止で

よく考えてみたら、 や が間に合うので、もっと思考停止した解法もとれる。問題文の言われるがままに

---

各辺 uv について、ある頂点 p, q が存在して

(p-q 間の最短路) = (p-u 間の最短路) + (uv 辺の長さ) + (v-q 間の最短路)

を満たすかどうかをチェックする

---

とするだけでよかった。ここで、「各 2 点の最短路」はあらかじめ Floyd-Warshall で前処理しておく。計算量は になる。ちょっと遅くなる。

#include <iostream>
using namespace std;
const int INF = 1<<29;
const int MAX_V = 110;
const int MAX_E = 1100;

int N, M;
int a[MAX_E], b[MAX_E], c[MAX_E]; // 各辺
int dist[MAX_V][MAX_V]; // Floyd-Warshall 用

int main() {
    cin >> N >> M;

    // Floyd-Warshall でよくやる初期化
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dist[i][j] = INF;
        }
        dist[i][i] = 0; // ここがポイント
    }

    // 入力
    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        --a[i], --b[i];
        dist[a[i]][b[i]] = c[i];
        dist[b[i]][a[i]] = c[i];
    }

    // Floyd-Warshall
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    // 集計
    int res = 0;
    for (int i = 0; i < M; ++i) {
        bool ok = false;
        for (int p = 0; p < N; ++p) {
            for (int q = 0; q < N; ++q) {
                if (dist[p][q] == dist[p][a[i]] + c[i] + dist[b[i]][q])
                    ok = true;
            }
        }
        if (!ok) ++res;
    }
    cout << res << endl;
}

解法 3: 最短路木

そもそも始点ノード を固定したときの、 から各頂点への最短路をすべて求める、という営みは Dijkstra 法しながら最短路木を求めることで実現できるので、それでもいい。

やるべきことは

• 意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法

を見ればわかると思う。つまり、最短路の復元に使われる可能性のある辺は OK ということになる。計算量は各頂点から Dijkstra 法を回すので、 になる。

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
const int INF = 1<<29;

// グラフ
using Edge = pair<int,long long>; // {辺の行き先, 重み}
using Graph = vector<vector<Edge> >; // グラフ

// 使われうる辺集合
set<pair<int,int> > use;

// s を始点とする Dijkstra
vector<long long> Dijkstra(const Graph &G, int s) {
    vector<long long> dist((int)G.size(), INF);
    vector<vector<int> > prev((int)G.size()); // prev[v] := v から復元できる辺たち
    dist[s] = 0;
    priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > que;
    que.push({0, s});
    while (!que.empty()) {
        auto cur = que.top(); que.pop();
        long long cur_dist = cur.first;
        int v = cur.second;
        if (cur_dist > dist[v]) continue; // 効く枝刈り
        for (auto e : G[v]) {
            if (dist[e.first] > dist[v] + e.second) {
                dist[e.first] = dist[v] + e.second;
                que.push({dist[e.first], e.first});

                // 復元のための
                prev[e.first].clear();
                prev[e.first].push_back(v);
            }
            else if (dist[e.first] == dist[v] + e.second) {
                prev[e.first].push_back(v);
            }
        }
    }

    // 使われうる辺集合
    for (int v = 0; v < (int)G.size(); ++v) {
        for (auto u : prev[v]) {
            use.insert(make_pair(min(u, v), max(u, v)));
        }
    }
    return dist;
}

int main() {
    int N, M; cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; long long c;
        cin >> a >> b >> c;
        --a, --b;
        G[a].push_back(Edge(b, c));
        G[b].push_back(Edge(a, c));
    }
    for (int v = 0; v < N; ++v) Dijkstra(G, v);
    cout << M - (int)use.size() << endl;
}

---

1. なぜなら、もし、取り除いたグラフ上の辺 uv に対して迂回路 u-a-b-c-...-v が存在して、その長さが uv よりも短いならば、uv は既に取り除かれているはずだからである。↩