自动搬运

查看原文

来自洛谷，原作者为

	JNK_DOG AFO on 2021.4.15

搬运于2025-08-24 21:39:44，当前版本为作者最后更新于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;
}