G8019 [GESP202603 八级] 消息查找 题解

知识点：坐标压缩、最短路、动态规划、二分查找。

解题思路

只保留有引用的消息编号及被引用编号，坐标压缩后，相邻坐标间倒退费用为编号差，引用边费用1。每个引用起点按编号递减做DAG最短路；查询先走到x左侧最近引用起点，再接压缩最短路并补最后一段。

为什么正确

所有边均指向较小编号，倒序松弛正确；没有引用的区间只可能逐条倒退，可压成带权边。必经最近引用起点，允许不跳引用也保留了其他路线。

易错点

不应把n个点做所有点最短路；查询还要比较完全步行x-y，最后目标可能不在压缩坐标内。

复杂度

引用数K≤1000、坐标数C≤2K，时间O(n+KC+q log C)，空间O(KC+n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<int>r(n+1),sources,coords;
    for(int i=1;i<=n;i++) {
        cin>>r[i];
        if(r[i]) {
            sources.push_back(i);
            coords.push_back(i);
            coords.push_back(r[i]);
        }
    }
    sort(coords.begin(),coords.end());
    coords.erase(unique(coords.begin(),coords.end()),coords.end());
    int K=sources.size(),C=coords.size();
    vector<vector<int>>d(K,vector<int>(C,1000000000));
    vector<int>target(C,-1);
    for(int s:sources) {
        int j=lower_bound(coords.begin(),coords.end(),s)-coords.begin();
        target[j]=lower_bound(coords.begin(),coords.end(),r[s])-coords.begin();
    }
    for(int i=0;i<K;i++) {
        int j=lower_bound(coords.begin(),coords.end(),sources[i])-coords.begin();
        d[i][j]=0;
        for(;j>=0;j--) {
            if(j)d[i][j-1]=min(d[i][j-1],d[i][j]+coords[j]-coords[j-1]);
            if(target[j]>=0)d[i][target[j]]=min(d[i][target[j]],d[i][j]+1);
        }
    }
    while(q--) {
        int x,y;
        cin>>x>>y;
        int idx=upper_bound(sources.begin(),sources.end(),x)-sources.begin()-1,ans=x-y;
        if(idx>=0&&sources[idx]>=y) {
            int j=lower_bound(coords.begin(),coords.end(),y)-coords.begin();
            ans=min(ans,x-sources[idx]+d[idx][j]+coords[j]-y);
        }
        cout<<ans<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用18个自行生成的测试点。