题解 P2620 虫洞

总体思路：离散化 + 建图 + 单源最短路
（看见人少蒟蒻才敢发题解QAQ)

---

需要注意的是：

1. 考虑到w范围较大，而实际虫洞数量较小，就只记录虫洞的起点与终点来建图。
2. 建图时，虫洞起点可以去重。
3. 在建图时b、e两点的距离并不一定为（e-b+s-1）/s。比如当我从0处走到6处，限定步数为3时，理论上是走2步，但如果3处有虫洞无法停留，则只能0->2->5->6走4步。

 #include <bits/stdc++.h>

 #define r(x) scanf("%d",&x)

 const int I=;

 using namespace std;

 set<int>s;//去重

 int w,st,p,c;

 int l[I*],x[I],y[I];//l[]为离散化数组，x[]为虫洞起点,y[]为虫洞终点

 int d[I*][I*];

 int F(int b,int e){//求解两点间距离

         if(b==e)return ;

         if(s.count(b))return 0x3fffffff;

         int k=e;

       for(int i=;i<=p;i++)

           if(b<x[i]&&x[i]<k&&(x[i]-b)%st==)k=x[i];//查找第一个落脚点

       while(k!=e&&s.count(k))k--;

       if(k==b)return 0x3fffffff;

       return F(k,e)+(k-b+st-)/st;

 }

 int Q(int x) {//由原点找离散化后的点

       return lower_bound(l+,l+c+,x)-l;

 }

 void Floyd(){//求解最短路

       for(int k=;k<=c;k++)

       for(int i=;i<=c;i++)

       for(int j=;j<=c;j++)

           d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

 }

 int main(){

       r(w);

       while(w!=){

           r(st);r(p);

           s.clear();

           memset(l,,sizeof l);

           memset(x,,sizeof x);

           memset(y,,sizeof y);

           c=;

           l[++c]=;l[++c]=w;

           for(int i=;i<=p;i++)

               r(x[i]),r(y[i]),s.insert(x[i]),l[++c]=x[i],l[++c]=y[i];

           sort(l+,l+c+);

           c=unique(l+,l+c+)-l-;

           memset(d,0x3f,sizeof d);

           for(int i=;i<=p;i++)

               d[Q(x[i])][Q(y[i])]=;//虫洞起终点距离为0

           for(int i=;i<c;i++)

           for(int j=i+;j<=c;j++)

               d[i][j]=min(d[i][j],F(l[i],l[j]));//初始化

           Floyd();

           cout<<d[][c]<<endl;

           r(w);

       }

       return ;

 }