题解：P3953 [NOIP 2017 提高组] 逛公园

· · 题解

一个非常经典的题目，可以看作记忆化搜索的板子题。

首先题目的限制与最短路有关，我们可以先求出每个点的最短路，方便后续处理。

其次我们发现题目中 K 的范围非常小，考虑将 K 这一维压入状态。设 f_{u,i} 表示从 1 到 u，距离为 d_u+i 的方案数，其中 d_u 是 1 到 u 的最短路。f_{1,0} 初始化为 1。

若 f_{u,i} 能从 f_{v,j} 转移而来，说明 d_u+i=d_v+j+w(u,v)，那么 j=d_u-d_v+i-w(u,v)。

接下来还有最后一个问题，如何判断无数解。我们发现，无数解的情况说明在图中有一个零环，在记忆化搜索的过程中，我们发现若一个状态能被其自己更新，说明存在零环，具体操作中只需要加一个 vis 判断即可。

最后在实现中要特别判断一下 k=0 的时候是否会使 f_{1,0} 取到无限，这个可以用样例测出来。下面给出代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
    int dis,u;
    bool operator<(node a)const{
        return a.dis<dis;
    }
};
struct jl{
    int v,w;
};
vector<jl>a1[N],a2[N];
int T,n,m,k,p,vis[N],dis[N],f[N][60],vvis[N][60],flag;
void dij(){
    priority_queue<node>q;
    for(int i=1;i<=n;i++){
        vis[i]=0;
        dis[i]=1e9;
    }
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int j=0;j<a1[u].size();j++){
            int v=a1[u][j].v,w=a1[u][j].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        } 
    }
}
int dfs(int u,int w){
    if(w<0)return 0;
    if(vvis[u][w]){
        flag=1;
        return 0;
    }
    if(f[u][w])return f[u][w];
    vvis[u][w]=1;
    int ans=0;
    for(int i=0;i<a2[u].size();i++){
        int v=a2[u][i].v,ww=a2[u][i].w;
        ans=(ans+dfs(v,dis[u]-dis[v]+w-ww))%p;
    }
    vvis[u][w]=0;
    return f[u][w]=ans;
}
signed main(){
    cin>>T;
    while(T--){
        int ans=0;
        cin>>n>>m>>k>>p;
        for(int i=1;i<=n;i++){
            a1[i].clear();
            a2[i].clear();
        }
        memset(f,0,sizeof f);
        memset(vvis,0,sizeof vvis);
        flag=0;
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            a1[u].push_back({v,w});
            a2[v].push_back({u,w});
        }
        dij();
        f[1][0]=1;
        if(k==0){
            dfs(n,1);
            if(flag){
                cout<<"-1\n";
                continue;
            }
        }
        for(int kk=0;kk<=k;kk++){
            ans=(ans+dfs(n,kk))%p;
        }
        if(flag)ans=-1;
        cout<<ans<<'\n';
    }
    return 0;
}