题解：P16824

好题。

我们先依次询问 $1 \rightarrow (2 \sim (n-1))$。

如果询问到 $1 \rightarrow i$ 的距离为 $1$，则我们可以直接输出 $i \rightarrow n$ 作为答案。为什么？因为根据三角不等式，$\lvert \operatorname{dist}(1,n) - \operatorname{dist}(v,n) \rvert \le \operatorname{dist}(v,n) = 1$。符合题目要求。

如果连一个距离为 $1$ 的点都没有询问到，则由于图连通，$1$ 必须和 $n$ 之间有边。直接输出 $1$ 即可。

💡 Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    if(n==2){
        printf("! 1");
        fflush(stdout);
        exit(0);
    }
    for(int i=2;i<n;i++){
        printf("? 1 %d\n",i);
        fflush(stdout);
        int v;
        scanf("%d",&v);
        if(v==1){
            printf("? %d %d\n",i,n);
            fflush(stdout);
            scanf("%d",&v);
            printf("! %d",v);
            fflush(stdout);
            exit(0);
        }
    }
    printf("! 1");
}