最短経路の復元 [Hokkaido University Programming Contest 2019 Day 1 E]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/E

解説

https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745712

説明のため、D[u][v] := 頂点uから頂点vへの最短経路としておく。

この問題を見たときに、大切な性質を思い出す。
D[S][x] + D[x][T] = D[S][T]となっているならば、SからTのある最短パスにxが含まれる。
これを使っていく。

まずは、Sから他の頂点、Tから他の頂点への最短距離を聞いておこう。
さっきの性質を使うと、最短パスに含まれる頂点を洗い出すことができる。
このとき、{D[S][x], x}というペアでvectorに入れておこう。
これでソートをかけると、最短距離が近い順にソートがかかる。 S, x1, x2, ..., Tという最短パスだった場合は、D[S][x1]＜D[S][x2]＜...となるはずである。
よって、このようにソートをかけておけば、順番を変えずに何個かとってきたときのどれかが最短パスになっている。

あとは、最短パスに含めることができる条件としては、S, ... x, ... y, ... Tという最短パスであるためには、D[S][T] = D[S][x] + D[x][y] + D[y][T]である必要がある。
よって、最短パスの最後に確定した頂点から、それよりも後の頂点とのサイズを測って、この条件が満たされるなら採用するというのを繰り返す。
これは質問をした後に、その頂点を採用するか使わず消すかの2択になるので、最大N回くらいの質問で実現できる。 よって、これで全体で3N回くらいしか質問しないので、AC

int N, S, T;
int A[303], B[303];
//---------------------------------------------------------------------------------------------------
map<pair<int, int>, int> memo;
int ask(int u, int v) {
    if (u == v) return 0;
    if (u > v) swap(u, v);

    if (memo.count({ u, v })) return memo[{u, v}];

    printf("? %d %d\n", u, v);
    fflush(stdout);

    int res; cin >> res;

    return memo[{u, v}] = res;
}
void answer(vector<int> v) {
    printf("!");
    fore(x, v) printf(" %d", x);
    printf("\n");
    fflush(stdout);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> T;

    rep(i, 1, N + 1) A[i] = ask(S, i);
    rep(i, 1, N + 1) B[i] = ask(T, i);

    vector<pair<int, int>> v;
    rep(i, 1, N + 1) if (A[T] == A[i] + B[i]) v.push_back({ A[i], i });
    sort(all(v));

    vector<int> ans;
    fore(p, v) {
        if (ans.size() == 0) ans.push_back(p.second);
        else {
            int pre = ans.back();
            if (A[T] == A[pre] + ask(pre, p.second) + B[p.second]) {
                ans.push_back(p.second);
            }
        }
    }
    answer(ans);
}