本文共 1441 字，大约阅读时间需要 4 分钟。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 仅一行，一个非负整数，表示从第1块跷跷板移动到第n块跷跷板的最小跳跃次数。

输入：

7

0 2 4 1 0 2 0 4 6 1 7 9 0 6 8 2 3 9 2 1 3

输出：

5

思路： 最短路 如果全部板块都相连的话，广搜求最短路就行了。 这里的模板可能有零散的话，存图的时候优化一下就行。 先将所有板块按照从上往下，从左往右排序。 对于任意一块模板k来说，只要考虑两种联结的情况，一是右边的模板，二是下一行的模板。 同行的模板考虑k+1即可，很容易想到。 下一行的模板考虑的时候有个小贪心,对于模板k来说，下一行与它相连的模板区间如果是第[l,r]块，考虑右边的模板k+1的下一行时，只要看区间[r-1,?]，不用从行头开始看。

//最短路#include
   
    using namespace std;typedef long long ll;queue 
    
      q;int tot=0,s=-1,z=-1;int head[100010];int dis[100010];struct ban{       int l,r,p,y;//左右边界，所在行，编号}a[100010];struct ty{       int next,t;}edge[2000010];void bfs(){       dis[s]=1;    q.push(s);    while( !q.empty() )    {           int x=q.front();        q.pop();        for(int i=head[x] ;i!=-1 ;i=edge[i].next)        {               int y=edge[i].t;            if(!dis[y])            {               q.push(y);            dis[y]=dis[x]+1;            }        }    }}bool cmp(ban a, ban b) //从上到下，从左到右排序{       if(a.y!=b.y)    return a.y
     
      >n;    for(int i=1; i<=n ;i++)    {           cin>>a[i].y>>a[i].l>>a[i].r;        a[i].p=i;    }    sort(a+1,a+1+n,cmp);//    for(int i=1; i<=n ;i++)//        cout<
      
       <<" ";//        cout<
       
        =a[i].r)  break;            if(a[l].r<=a[i].l)  continue;            addedge(i,l);            addedge(l,i);        }        if( l >1 )  l--;    }        //存完图，广搜求最短路    bfs();    cout<
        
         <