题解 P3953 【逛公园】

· · 题解

题意:求dis(1,n)<=MinDis(1,n)+K的路径数

算法一:

首先你可以考虑到Day1的DP去哪里了?

没错,你只要再注意一下K\le50就大概能想到这是一个与k有关的DP了

①:考虑30pts:K=0

右转P1608路径统计(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了