题解 P3953 【逛公园】

题意:求$dis(1,n)<=MinDis(1,n)+K$的路径数 ## 算法一: 首先你可以考虑到$Day1$的$DP$去哪里了? 没错,你只要再注意一下$K\le50$就大概能想到这是一个与$k$有关的$DP$了 #### ①:考虑$30pts:K=0 $ 右转[P1608路径统计](https://www.luogu.org/problemnew/show/P1608)([P1144最短路计数](https://www.luogu.org/problemnew/show/P1144)可以顺带A掉) #### ②:考虑$70pts$:没有$0$边 设$dis1_u$表示1到u的最短路,$disn_u$表示$u$到$n$的最短路(这个可以建反图跑出来) 考虑$f[u][j]$表示$dis(1,u)\le dis1_u+j$的路径数 那么对于$edge(u,v,w)$ 那么从$1->u->v$这条路径的长度就是$dis1_u+j+w-dis1_v$ 如果$dis1_u+w-dis1_v+j\le K$ 就可以从$f[u][j]$转移到$f[v][dis1_u+j+w-dis1_v]$ 所以直接先从$1$跑最短路然后直接$O(KM)DP$就$ok$了 当然这样还是有问题的 因为我们必须要先更新$dis1$小的点 所以要先按照$dis1$排个序再去转移就有$70pts$了 #### ③:考虑$100pts:$ 对于有$0$边的图,显然直接按照$dis1$去排序是不行的 例如$a->b->c,w=0$ 因为他的一个有向图,更新顺序显然是$a,b,c$ 所以考虑拓扑排序来确定$0$边两个端点的更新顺序 即对于$0$边,把其加入新图,然后对于新图拓扑排序确定"$0$点"的更新顺序 然后对于$-1$的情况显然是对于一条满足条件的路径上有一个$0$环 拓扑排序完了且入度不等于$0$说明这个点在$0$环上 同一个$0$环上任意一个点到$1$的最短路和到$n$的最短路都一样 所以当这个点$i$满足$dis1_i+disn_i<=dis1_n+K$时,就可以输出$-1$了 然后最后以$dis1$或$disn$为第一关键字,拓扑序为第二关键字排序再转移就$ok$了 ## 算法二: 只要跑一次反向的最短路 $f[u][k]$表示$dis(u,n)<=MinDis(u,n)+k$的方案数,答案就是$f[1][K]$ 考虑$egde(u,v,w)$ 同样的道理走这条边的话,$dis(v,n)=MinDis(v,n)+w-MinDis(u,n)$ $\Rightarrow f[u][k]=∑f[v][k-(MinDis(v,n)-MinDis(u,n)+w)]$ 这样怎么判$0$环呢?只要在搜索的时候记录个$instack$就$ok$了 如果当前的$v$还在搜索的栈中就可以直接返回$-1$了