[关闭]
@ysner 2018-09-16T14:50:03.000000Z 字数 2037 阅读 1919

[luogu2620]虫洞

最短路


题面

给一个一维坐标系,出发点为,目标点为
秒可以往后移不超过个单位距离。
现有个虫洞,可以把你从瞬移到
问最少多少秒可从出发点到目标点。

解析

注意到个点中很多点是没有意义的。
有意义的是那个虫洞,只有它们可以强行改变答案。
考虑用这个虫洞新建一张图。
这需要我们思考,从一个虫洞的终点到另一个虫洞的起点的距离。
轴上它们间距离为
为从当前点开始,到达距离模的点的最短距离。
先定一个虫洞,然后枚举第二个虫洞。
然后不断用上一个虫洞终点的更新这一个虫洞终点的即可。
最后把,代表不能用其更新下一次答案。

需要注意的是,如果有个虫洞的起点连续成段,后面的虫洞就走不到了。

接下来解决。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=2e3+100,inf=2e9;
  15. int tar,h[50],cnt,s,n,st[50],f[10],g[10];
  16. ll dis[50];
  17. bool vis[50];
  18. struct Edge{int to,nxt,w;}e[N<<1];
  19. struct hol{int l,r;bool operator < (const hol &o) const {return l<o.l;}}a[N];
  20. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  21. il ll gi()
  22. {
  23. re ll x=0,t=1;
  24. re char ch=getchar();
  25. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26. if(ch=='-') t=-1,ch=getchar();
  27. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28. return x*t;
  29. }
  30. il int ban(re int x)
  31. {
  32. fp(i,0,s-1)
  33. if(x-i>=0&&st[lower_bound(st+1,st+1+n,x-i)-st]!=x-i) return 0;
  34. return 1;
  35. }
  36. il int calc(re int x){return (x+s-1)/s;}
  37. il void Build(re int x)
  38. {
  39. f[0]=0;
  40. fp(i,1,s-1) f[i]=1;
  41. re int las=0,len,yu;
  42. fp(i,1,n)
  43. if(i!=x&&a[i].l>=a[x].r)
  44. {
  45. fp(j,0,s-1) g[j]=inf;
  46. len=a[i].l-a[x].r;
  47. yu=len/s;
  48. fp(j,0,s-1)
  49. fp(k,0,s-1)
  50. if(yu*s+k>=las*s+j) g[k]=min(g[k],f[j]+calc(yu*s+k-las*s-j));
  51. add(x,i,g[len%s]);
  52. g[len%s]=inf;
  53. fp(j,0,s-1) f[j]=g[j];
  54. las=yu;
  55. if(ban(a[i].l)) return;
  56. }
  57. }
  58. il void SPFA(re int S)
  59. {
  60. queue<int>Q;
  61. fp(i,1,n) dis[i]=inf;
  62. dis[S]=0;vis[S]=1;Q.push(S);
  63. while(!Q.empty())
  64. {
  65. re int u=Q.front();Q.pop();
  66. for(re int i=h[u];i+1;i=e[i].nxt)
  67. {
  68. re int v=e[i].to;
  69. if(dis[v]>dis[u]+e[i].w)
  70. {
  71. dis[v]=dis[u]+e[i].w;
  72. if(!vis[v]) Q.push(v),vis[v]=1;
  73. }
  74. }
  75. vis[u]=0;
  76. }
  77. }
  78. int main()
  79. {
  80. while(233)
  81. {
  82. tar=gi();if(!tar) return 0;
  83. memset(h,-1,sizeof(h));cnt=0;
  84. s=gi();n=gi();
  85. fp(i,1,n) a[i].l=gi(),a[i].r=gi();
  86. sort(a+1,a+1+n);
  87. a[n+1].l=a[n+1].r=0;
  88. a[n+2].l=a[n+2].r=tar;
  89. n+=2;
  90. fp(i,1,n) st[i]=a[i].l;
  91. fp(i,1,n) Build(i);
  92. SPFA(n-1);
  93. printf("%lld\n",dis[n]);
  94. }
  95. return 0;
  96. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注