题解：P16823 [AFOI 2025] A1.追忆（Easy Version）

Ethan_sun · 2026-06-07 10:30:48 · 题解

solution

注意到我们能直接询问除了 1 到 n 的最短路，那么我们可以把剩下的 n - 2 个点当作中间节点，每次询问 1 到 i 的最短路和 i 到 n 的最短路，把返回的答案加起来取最小值。

然后只有答案是 3 的情况下，其实际答案是 1，特判一下就过了。

code

::::success[展开]

#include <bits/stdc++.h>
#define debug(a) cerr << (#a) << " = " << (a) << endl;
#define int long long
#define maxn 100010
// #define endl '\n'
using namespace std;

int n;
void solve() {
    cin >> n;
    int ans = n - 1;
    for (int i = 2; i < n; i++) {
        cout << "? " << 1 << " " << i << endl;
        int a; cin >> a;
        cout << "? " << i << " " << n << endl;
        int b; cin >> b;
        ans = min(ans, a + b);
    }
    if (ans == 3) cout << "! 2" << endl;
    else cout << "! " << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
//  cin >> t;
    while (t--) solve();
    return 0;
}

::::