题解 P2620 【虫洞】

JNK_DOG · 2019-08-02 15:15:01 · 题解

总体思路：离散化 + 建图 + 单源最短路

（看见人少蒟蒻才敢发题解QAQ）

需要注意的是：

• 考虑到w范围较大，而实际虫洞数量较小，就只记录虫洞的起点与终点来建图。
• 建图时，虫洞起点可以去重。
• 在建图时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=50;
  using namespace std;
  set<int>s;//去重
  int w,st,p,c;
  int l[I*2],x[I],y[I];//l[]为离散化数组，x[]为虫洞起点,y[]为虫洞终点
  int d[I*2][I*2];
  int F(int b,int e){//求解两点间距离
      if(b==e)return 0;
      if(s.count(b))return 0x3fffffff;
      int k=e;
    for(int i=1;i<=p;i++)
        if(b<x[i]&&x[i]<k&&(x[i]-b)%st==0)k=x[i];//查找第一个落脚点
    while(k!=e&&s.count(k))k--;
    if(k==b)return 0x3fffffff;
    return F(k,e)+(k-b+st-1)/st;
  }
  int Q(int x) {//由原点找离散化后的点
    return lower_bound(l+1,l+c+1,x)-l;
  }
  void Floyd(){//求解最短路
    for(int k=1;k<=c;k++)
    for(int i=1;i<=c;i++)
    for(int j=1;j<=c;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  }
  int main(){
    r(w);
    while(w!=0){
        r(st);r(p);
        s.clear();
        memset(l,0,sizeof l);
        memset(x,0,sizeof x);
        memset(y,0,sizeof y);
        c=0;
        l[++c]=0;l[++c]=w;
        for(int i=1;i<=p;i++)
            r(x[i]),r(y[i]),s.insert(x[i]),l[++c]=x[i],l[++c]=y[i];
        sort(l+1,l+c+1);
        c=unique(l+1,l+c+1)-l-1;
        memset(d,0x3f,sizeof d);
        for(int i=1;i<=p;i++)
            d[Q(x[i])][Q(y[i])]=0;//虫洞起终点距离为0
        for(int i=1;i<c;i++)
        for(int j=i+1;j<=c;j++)   
            d[i][j]=min(d[i][j],F(l[i],l[j]));//初始化
        Floyd();
        cout<<d[1][c]<<endl;
        r(w);
    }
    return 0;
  }