https://www.zybuluo.com/ysner/note/1284536
题面
给一个一维坐标系，出发点为(0)，目标点为(w)。
每(1)秒可以往后移不超过(s)个单位距离。
现有(p)个虫洞，可以把你从(s_i)瞬移到(t_i)，
问最少多少秒可从出发点到目标点。
- (wleq10^9,2leq sleq6,pleq40)
解析
注意到(w+1)个点中很多点是没有意义的。
有意义的是那(p)个虫洞，只有它们可以强行改变答案。
考虑用这(p)个虫洞新建一张图。
这需要我们思考，从一个虫洞的终点到另一个虫洞的起点的距离。
设(x)轴上它们间距离为(len)。
设(f[i])为从当前点开始，到达距离模(s)为(i)的点的最短距离。
先定一个虫洞，然后枚举第二个虫洞。
然后不断用上一个虫洞终点的(f[i])更新这一个虫洞终点的(f[i])即可。
最后把(f[len\%s]=inf)，代表不能用其更新下一次答案。
需要注意的是，如果有(s)个虫洞的起点连续成段，后面的虫洞就走不到了。
接下来(SPFA)解决。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e3+100,inf=2e9;
int tar,h[50],cnt,s,n,st[50],f[10],g[10];
ll dis[50];
bool vis[50];
struct Edge{int to,nxt,w;}e[N<<1];
struct hol{int l,r;bool operator < (const hol &o) const {return l<o.l;}}a[N];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int ban(re int x)
{
fp(i,0,s-1)
if(x-i>=0&&st[lower_bound(st+1,st+1+n,x-i)-st]!=x-i) return 0;
return 1;
}
il int calc(re int x){return (x+s-1)/s;}
il void Build(re int x)
{
f[0]=0;
fp(i,1,s-1) f[i]=1;
re int las=0,len,yu;
fp(i,1,n)
if(i!=x&&a[i].l>=a[x].r)
{
fp(j,0,s-1) g[j]=inf;
len=a[i].l-a[x].r;
yu=len/s;
fp(j,0,s-1)
fp(k,0,s-1)
if(yu*s+k>=las*s+j) g[k]=min(g[k],f[j]+calc(yu*s+k-las*s-j));
add(x,i,g[len%s]);
g[len%s]=inf;
fp(j,0,s-1) f[j]=g[j];
las=yu;
if(ban(a[i].l)) return;
}
}
il void SPFA(re int S)
{
queue<int>Q;
fp(i,1,n) dis[i]=inf;
dis[S]=0;vis[S]=1;Q.push(S);
while(!Q.empty())
{
re int u=Q.front();Q.pop();
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v]) Q.push(v),vis[v]=1;
}
}
vis[u]=0;
}
}
int main()
{
while(233)
{
tar=gi();if(!tar) return 0;
memset(h,-1,sizeof(h));cnt=0;
s=gi();n=gi();
fp(i,1,n) a[i].l=gi(),a[i].r=gi();
sort(a+1,a+1+n);
a[n+1].l=a[n+1].r=0;
a[n+2].l=a[n+2].r=tar;
n+=2;
fp(i,1,n) st[i]=a[i].l;
fp(i,1,n) Build(i);
SPFA(n-1);
printf("%lld
",dis[n]);
}
return 0;
}