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

I_do_Cpp · 2026-06-07 10:35:24 · 题解

博客观看效果更佳。

前言

我常常追忆过去。

第一次场切交互题祭。

题目解析

我们可以采取 floyd 算法的方式，枚举中间点来转移 1 到 n 的最短路，即 f_{1,n}=\min_{1<k<n} f_{1,k}+f_{k,n}，其中 f_{i,j} 表示从 i 到 j 的最短路长度。注意，一般情况下，这种计算答案是完全正确、没有误差的，除非有下面的情况。

但是有个糟糕的情况就是 1 到 n 直接联通并且图是个环的情况，这样你无论怎么搜答案都是 3。不妨利用绝对值差为 1 即通过的规则，将答案减 1，这样和任何情况的答案都差了 1，可以通过。

记得特判 n=2 时直接输出 1，否则你的程序会输出极大值。

正解代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n,ans=INT_MAX;
    cin>>n;
    for(int i=2;i<n;i++)
    {
        int x,y;
        cout<<"? 1 "<<i<<endl;
        cin>>x;
        cout<<"? "<<i<<" "<<n<<endl;
        cin>>y;
        ans=min(ans,x+y);
    }
    cout<<"! "<<(n!=2?ans-1:1);
    return 0;
}