結果

問題 No.3463 Beltway
コンテスト
ユーザー InTheBloom
提出日時 2026-02-28 16:05:10
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
AC  
実行時間 295 ms / 2,000 ms
コード長 3,028 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,213 ms
コンパイル使用メモリ 172,364 KB
実行使用メモリ 61,712 KB
最終ジャッジ日時 2026-02-28 16:05:18
合計ジャッジ時間 7,843 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std;

void main () {
    int V, E, S, G;
    readln.read(V, E, S, G);
    S--, G--;
    auto A = new int[](E);
    auto B = new int[](E);
    foreach (i; 0 .. E) {
        readln.read(A[i], B[i]);
        A[i]--, B[i]--;
    }

    auto graph = new int[][](V);
    foreach (i; 0 .. E) {
        graph[A[i]] ~= B[i];
        graph[B[i]] ~= A[i];
    }

    // とりあえずBFSしてSからの距離をはかっておく、そして(u, v)であってdist[u] + 1 = dist[v]であるところのみ有向辺を貼る。
    // そのグラフはDAGを成すので、その上でdp[i] := Sから最短のいずれかの道を辿ったとき、橋を最小何本通るかを求める
    // lowlinkで橋かどうかの判定ができるのでこれでOK

    auto dist = new int[](V);
    auto q = DList!(int)();
    dist[] = int.max;
    q.insertBack(S);
    dist[S] = 0;
    while (!q.empty()) {
        auto pos = q.front();
        q.removeFront();
        foreach (to; graph[pos]) {
            if (dist[to] == int.max) {
                dist[to] = dist[pos] + 1;
                q.insertBack(to);
            }
        }
    }

    if (dist[G] == int.max) {
        writeln(-1);
        return;
    }

    // lowlink（窃盗 from https://algo-logic.info/bridge-lowlink/）
    bool[Tuple!(int, int)] bridge;
    auto used = new bool[](V);
    auto ord = new int[](V);
    auto low = new int[](V);

    int dfs (int id, int k, int par) { // id:探索中の頂点, k:dfsで何番目に探索するか, par:idの親
        used[id] = true;
        ord[id] = k++;
        low[id] = ord[id];
        int count = 0; // 子の数
        foreach (e; graph[id]) {
            if (!used[e]) {
                count++;
                k = dfs(e, k, id);
                low[id] = min(low[id], low[e]);
                if (ord[id] < low[e]) bridge[tuple(min(id, e), max(id, e))] = true; // 条件を満たすので橋
            } else if (e != par) { // eが後退辺の時
                low[id] = min(low[id], ord[e]);
            }
        }
        return k;
    }

    {
        int k = 0;
        foreach (i; 0 .. V) {
            if (!used[i]) {
                k = dfs(i, k, -1);
            }
        }
    }

    auto memo = new int[](V);
    memo[] = -1;
    int dp (int x) {
        if (memo[x] != -1) {
            return memo[x];
        }
        if (x == S) {
            return 0;
        }
        int ret = int.max;

        foreach (to; graph[x]) {
            if (dist[to] != dist[x] - 1) {
                continue;
            }
            int add = 0;
            auto e = tuple(min(x, to), max(x, to));
            if (e in bridge) {
                add = 1;
            }

            ret = min(ret, dp(to) + add);
        }

        return memo[x] = ret;
    }

    writeln(dist[G] - dp(G));
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0