题解：P16824 [AFOI 2025] A2.追忆（Hard Version）

Deepsick · 2026-06-07 22:05:48 · 题解

记节点 i 到 j 的最短路为 d_{i,j}。注意到对于任意节点 i,j,k，有 d_{i,j}+d_{j,k}\ge d_{i,k}。

所以，可以询问从 1 到每个点的距离。如果存在点 x 使得 d_{1,x}=1，则必有 d_{1,n}\in[d_{x,n}-1,d_{x,n}+1]，所以询问 d_{x,n} 并输出即可。

如果不存在这样的 x，则说明 1 到除 n 以外的点都不存在边。由连通性知 1 到 n 必存在边，所以答案为 1。 ::::success[AC 代码]

#include <iostream>
using namespace std;
int main() {
    int n,i,x;
    cin>>n;
    for(i=2;i<n;i++) {
        cout<<"? 1 "<<i<<endl;
        cin>>x;if(x==1) break;
    }
    if(i==n) {cout<<"! 1"<<endl;return 0;}
    cout<<"? "<<i<<' '<<n<<endl;
    cin>>x;cout<<"! "<<x<<endl;
    return 0;
}

:::: AC 记录。