牛牛与跷跷板

抓住题目中：相邻则可以跳跃，目的是寻求1号块到n号的最小跳跃次数

可以确定这道题的基本解法是：最短路

然后在题目的思考过程中发现，这道题的图并没有给你构造出来

那就需要从零开始构建边与边之间的关系

第一发想到的当然是暴力构建，N^2 的复杂度果然超了……

随后发现，这题居然可以贪一贪！

怎么贪呢，分两种情况：

① *：Y坐标相同时，只有贴在一起的块能相互连通，这个非常好处理

② *：Y坐标不同时，我们从Y==0算起，每次只判断Y行和Y+1的快是否互相连通，当推到最大的Y坐标是能，整个图也就构建完成了

这样做就要把每行的元素都排个序，所以就用vector数组存数据了，数组编号就是y轴坐标。

然后把最短路板子套进去就ok了

（最短路用的y总的板子，改都没改，所以说这一题关键还是在于选择什么样的构建方案）

那么看代码，细节我已经注释上去了

#include<iostream>
#include<algorithm>
#include<vector> 
#include<cstring>
#include<queue>
using namespace std;
struct Node{//节点定义，分别是编号，y坐标，左右x坐标
    int id,py,px1,px2;
    bool operator<(const Node &M)const {return px1<M.px1;}
};
int dist[200005],n,maxr;//dist是最短路的数组，maxr是最大y坐标
bool st[200005];//最短路模板
vector<int> g[200005];//构建的邻接表
vector<Node>li[100005];//存储输入信息
void uni(int i,int j){ g[i].push_back(j); g[j].push_back(i); }//邻接表中链接i，j
int dijkstra(){//dij求最短路，模板
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号
    while (heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        for (auto i = g[ver].begin(); i != g[ver].end(); i ++){
            int j = *i;
            if (dist[j] > distance + 1){
                dist[j] = distance + 1;
                heap.push({dist[j], j});
            }
        }
    }
    return dist[n];
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){//存储输入信息和记录最大y坐标
        int x,y,z;cin>>x>>y>>z;
        li[x].push_back({i,x,y,z});
        maxr=max(maxr,x);
    }
    for(int i=0;i<=maxr;i++){//①*
        sort(li[i].begin(),li[i].end());//每行排序
        for(int j=1;j<li[i].size();j++) 
            if(li[i][j-1].px2==li[i][j].px1) //横向相邻即链接
                uni(li[i][j-1].id,li[i][j].id);
    }
    for(int i = 0; i <= maxr; i++) {//②*
        auto p1 = li[i].begin(), p2 = li[i + 1].begin();//p1,p2代表前后两行
        while(p1 != li[i].end() && p2 != li[i + 1].end()) {//直到数完一行所有的元素
            if(max(p1->px1, p2->px1) < min(p1->px2, p2->px2)) 
                uni(p1->id,p2->id);//满足有接触，链接
            if(p1->px2 <= p2->px2) p1++;//推进到下一对判断
            else p2++;
        }
    }
    cout<<dijkstra();//最短路求结果
}

（太菜了我QAQ，这道题比赛时死磕3小时最后还是没做出来，只a了一道题的签到选手太惭愧了）