[关闭]
@rebirth1120 2019-11-11T15:56:05.000000Z 字数 2153 阅读 619

[NOIP2017 逛公园] 解题报告

解题报告 NOIP


NOIP2017 逛公园

这道题看了第三遍了, 还是想不出来.
写篇记录增强一下印象吧.

题意

有一张 个点, 条边的有向图 , 没有自环和重边,
每一条边都有一个非负权值,
为节点 到节点 的最短路, 求 的路径中长度不超过 的路径数量 .

思路

第一次看这道题是大概一年前了, 完全没有思路, 抄了篇题解走人.

第二次稍微有点思路, 但是跑偏了, 总向着 那个方向来统计数量, 并且也不太懂怎么判 环, 最后还是看了自己第一次的代码.

这一次又看了这道题, 思路还是和第二次差不多, 实在觉得不行, 还是要写一篇解题记录.

这次又看了一遍, 才发现这题实际上是一道搜索题, 设状态, 然后记忆化搜索, 顺便判 环.

有两个问题不是那么明了:
1. 为什么要从 开始搜索?
2. 为什么 要从小到大搜索?

第一个问题, 我的理解是 :
假设从 开始搜索, 我们就只知道当前点到起点的距离, 对于它能否到达终点我们是无法直接判断的.

而从 开始搜索的话, 就可以直接判断它是否能到达终点, 并及时停止进一步无用的搜索.

当然, 在反向边上跑最短路然后从 开始搜也是可以的, 相当于交换了起点和终点.

第二个问题 :
其实从大到小也是可以的....

代码

第二次的代码

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<queue>
  5. #define ll long long
  6. using namespace std;
  7. const int N=100000+7;
  8. const int M=200000+7;
  9. const int K=50+7;
  10. int T,n,m,k;
  11. ll p,f[N][K],ans;
  12. bool b[N],be[N][K],re[N][K],flag;
  13. int dis[N];
  14. int lst[N],nxt[M],to[M],len[M],tot;
  15. int rlst[N],rnxt[M],rto[M],rlen[M],rtot;
  16. void add(int x,int y,int w){
  17. nxt[++tot]=lst[x];
  18. to[tot]=y;
  19. len[tot]=w;
  20. lst[x]=tot;
  21. }
  22. void radd(int x,int y,int w){
  23. rnxt[++rtot]=rlst[x];
  24. rto[rtot]=y;
  25. rlen[rtot]=w;
  26. rlst[x]=rtot;
  27. }
  28. void read(){
  29. tot=rtot=0;
  30. memset(lst,0,sizeof(lst));
  31. memset(rlst,0,sizeof(rlst));
  32. scanf("%d%d%d%lld\n",&n,&m,&k,&p);
  33. int x,y,w;
  34. for(int i=1;i<=m;i++){
  35. scanf("%d%d%d",&x,&y,&w);
  36. add(x,y,w);
  37. radd(y,x,w);
  38. }
  39. }
  40. queue<int> q;
  41. void dijkstra(){
  42. memset(dis,0x3f,sizeof(dis));
  43. memset(b,0,sizeof(b));
  44. priority_queue<pair<int,int> > h;
  45. h.push(make_pair(0,1));
  46. dis[1]=0;
  47. while(!h.empty()){
  48. int u=h.top().second; h.pop();
  49. if(b[u]) continue;
  50. b[u]=1;
  51. for(int i=lst[u];i;i=nxt[i]){
  52. int v=to[i];
  53. if(dis[v]>dis[u]+len[i]){
  54. dis[v]=dis[u]+len[i];
  55. h.push(make_pair(-dis[v],v));
  56. }
  57. }
  58. }
  59. }
  60. int clac(int u,int r){
  61. if(r<0) return 0;
  62. if(re[u][r]){
  63. flag=1;
  64. return 0;
  65. }
  66. if(be[u][r]) return f[u][r];
  67. re[u][r]=1;
  68. for(int i=rlst[u];i;i=rnxt[i]){
  69. int v=rto[i],dif=dis[v]+rlen[i]-dis[u];
  70. f[u][r]=(f[u][r]+clac(v,r-dif))%p;
  71. if(flag) return 0;
  72. }
  73. be[u][r]=1;
  74. re[u][r]=0;
  75. return f[u][r];
  76. }
  77. int main(){
  78. //freopen("park.in","r",stdin);
  79. //freopen("park.out","w",stdout);
  80. cin>>T;
  81. while(T--){
  82. read();
  83. dijkstra();
  84. memset(be,0,sizeof(be));
  85. memset(re,0,sizeof(re));
  86. memset(f,0,sizeof(f));
  87. f[1][0]=1;
  88. be[1][0]=1;
  89. flag=0;
  90. ans=0;
  91. for(int i=0;i<=k;i++){
  92. ans=(ans+clac(n,i))%p;
  93. if(flag) break;
  94. }
  95. if(flag) printf("-1\n");
  96. else printf("%lld\n",ans);
  97. }
  98. return 0;
  99. }
  100. /*
  101. 1
  102. 5 10 0 624775377
  103. 1 2 1
  104. 2 5 2
  105. 2 4 1
  106. 5 4 2
  107. 4 2 1
  108. 4 5 2
  109. 2 3 1
  110. 3 2 1
  111. 1 3 2
  112. 3 5 1
  113. */
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注