P3953题解 记忆化搜索

· · 题解

做完这题后我看了大部分题解（我太弱了,交了15次才过），发现大多数题解都被新数据hack掉了，按时间排序后发现前几位大佬的做法都十分优越，但没有一个是像我一样跑一次最短路+没有剪枝的记忆化搜索就跑过的，就想来写一篇题解。

这题的部分分带有十足的引导性,但前面的部分分以前的题解已经讲的很清楚了，所有我们就直接从没有零边的情况开始（也就是 70pts ）。

发现 k 最大才50！

看到 k 比较小，就用 k 作为动规的一维，再考虑另一维，可以选择点或边——果断选 A （从来没有用边转移过，也可能是我没想到）。

怎么 dp ？

想这应该是想好 dp 的维度后应最优先考虑的问题，先仔细读题，我们求路程的总长度要满足条件

首先先跑一边最短路必不可少（~~这是废话~~，建议使用 Dijkstra+堆优化，SPFA 容易被卡）,再对每一条边进行转移。 设 $dis[i]$ 表示从 $1$ 到 $i$ 的最短路，$dp[i][j]$ 为比 $dis[i]$ 正好多 $j$ 为长度的方案总数（前面都分析过了）。 再考虑方程（动规真不用背方程）。 假设有一条从 $p$ 到 $now$ 长度为 $w$ 的一条边 目标：将 $dp[p][x]$ 转移到 $dp[now][k]$ ( $k$ 为比最短路多出的长度) 可以发现只有 $x$ 是不知道的量。 可以得出 $x-k=dis[now]-dis[p]-w

再将 k 移过去

x=dis[now]-dis[p]+k-b[p]

转移条件具备，目标达成

JOJO,这是我最后的方程了:

dp[now][k]=(dp[now][k]+dp[p][x]) \, mod \, p

（最后不要忘了 mod \, p 哦）

实际做的时候我们枚举 k 进行搜索，为了保证时间，我们还要加上记忆化（又是废话）。

重点

我们在记忆化搜索和求最短路时可以只建立单向边，毕竟都不会再往回跑，然后就是别用同一张图，记忆化搜索时要反向建边，从终点开始搜，这样才可以保证 dp 的正确性（不会证明，望大佬补充）。

看到这里可以先去尝试实现以一下（我知道这是不可能的）。

最后考虑有零边，也就是无限的情况，其实就是考虑有没有零边所构成的环（没有零环就一定是有限的），判断方法异常简单，就是像 SPFA dfs 判负环一样，用一个 vis 数组记录一下，现在的状态是否出现过，这是就可以输出 -1 了。

以上就是这题的解法，其他大佬有 tarjan,topu,dfs+ 剪枝...但只有我的方法只用了一次最短路+无剪枝记忆化搜索就过了的（让我小骄傲一下），但时间普遍比其他方法慢 100-300ms 所以建议还是多看几篇题解（真是道好题）

最后附上 AC 记录和代码

AC了哦

Code 
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
const int maxk=55;
inline int read(){
    int x=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
int n,p;
int a[maxn],b[maxn],nxt[maxn],head[maxn],cnt;
int A[maxn],B[maxn],NXT[maxn],HEAD[maxn],CNT;
bool flag;  
int dp[maxn][maxk];
inline void addline(int x,int y,int z){
    a[++cnt]=y,b[cnt]=z,nxt[cnt]=head[x],head[x]=cnt;
}
inline void ADDLINE(int x,int y,int z){
    A[++CNT]=y,B[CNT]=z,NXT[CNT]=HEAD[x],HEAD[x]=CNT;
}
int dis[maxn];
struct nn{
    int d,id;
    bool operator < ( const nn &A ) const{ return d>A.d; };
};
priority_queue<nn> pq;
inline void dijkstra(int s){
        for(register int i=1;i<=n;++i) dis[i]=0x3f3f3f3f;
        dis[s]=0; pq.push((nn){0,s});
        while(!pq.empty()){
            nn now=pq.top(); pq.pop();
            int val=now.d,u=now.id;
            if(dis[u]<val) continue;
            for(register int p=head[u]; p ;p=nxt[p]){
                int v=a[p];
                    if(dis[v]>dis[u]+b[p]){
                        dis[v]=dis[u]+b[p];
                        pq.push((nn){dis[v],v});
                    }
            }
        }
}
bool vis[maxn][maxk];
int dfs(int now,int k){
//    cout<<now<<" "<<k<<endl;
    if(~dp[now][k]) return dp[now][k];
    dp[now][k]=0,vis[now][k]=1;
    for(register int i=HEAD[now]; i ;i=NXT[i]){
        int v=A[i];
        int x=dis[now]-dis[v]+k-B[i];
        if(x<0) continue;
        if(vis[v][x]) flag=1;
        dp[now][k]=(dp[now][k]+dfs(v,x))%p;
    }
    vis[now][k]=0;
    return dp[now][k];
}
/*
    dp[p][x]->dp[now][k]
    x=dis[now]-dis[p]+k-b[p]
*/ 
int m,k;
int main(){
    int T=read();
    while(T--){
        n=read(),m=read(),k=read(),p=read();
        cnt=CNT=flag=0;
        memset(head,0,sizeof head);
        memset(HEAD,0,sizeof HEAD);
        memset(dp,-1,sizeof dp);
        for(register int i=1;i<=m;++i){
            int u=read(),v=read(),w=read();
            addline(u,v,w),ADDLINE(v,u,w);
        }
        dijkstra(1);
        for(register int i=0;i<=k;++i) dfs(n,i);
        if(flag) { printf("-1\n"); continue; }
        int ans=0;
        memset(dp,-1,sizeof dp); dp[1][0]=1;
        for(register int i=0;i<=k;++i){
            ans=(ans+dfs(n,i))%p;
        }
        printf("%d\n", ans);
    }
    return 0;
}