lp3953 NOIP2017 逛公园

容易知道，对于每个点，最多只能偏移50。
由此可以跑记忆化搜索：\(f_{i,j}\)表示，在第i个点，比最短路长了j时的方案数。
那么，我们倒着搜即可。
具体来说，定义\(dn_{x}\)表示\(x->u\)的最短路。
那么我们可以得到状态转移方程：
$$f_{u,k}=\sum_{v,v\in S,st: \forall x \in S,x_{u}=u}f_{v,k-dn_{v}+dn_{u}-w}$$
答案为\(f_{1,K}\)
几个细节：
e[i].nxt不应写作e[i].v
不要使用长得差不多的变量。

#include<iostream>
#include<cstdio>
#include<queue> 
#include<cstring>
using namespace std;
struct ee{
    int v;
    int w;
    int nxt;
}e[400005];
int h[100005],h2[100005],et=0,n,m,K,p,dis[100005],dn[100005],f[100005][51];
bool usd[100005][51];
inline void add(int *_H,const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,_H[u]};
    _H[u]=et;
}
struct cmp2{
    inline bool operator ()(const int &X,const int &Y)const{
        return dn[X]>dn[Y];
    }
};
void dij2(){
    priority_queue< int,vector<int>,cmp2 > q;
    memset(dn,0x3f,sizeof(dn));
    dn[n]=0;
    q.push(n);
    int nw;
    while(!q.empty()){
        nw=q.top();
        q.pop();
        for(int i=h2[nw];i;i=e[i].nxt){
            if(dn[e[i].v]>dn[nw]+e[i].w){
                dn[e[i].v]=dn[nw]+e[i].w;
                q.push(e[i].v);
            }
        }
    }
}
int dfs(int u,int k){
    if(usd[u][k]){
        return -1;
    }
    if(f[u][k]){
        return f[u][k];
    }
    usd[u][k]=1;
    if(u==n){
        f[u][k]=1;
    }
    int X,sm;
    for(int i=h[u];i;i=e[i].nxt){
        //e[i].v不能写成e[i].nxt 
        sm=dn[e[i].v]-dn[u]+e[i].w;
        if(sm>k){
            continue;
        }
        X=dfs(e[i].v,k-sm);
        if(X==-1){
            return f[u][k]=-1;
        }
        f[u][k]+=X;
        f[u][k]%=p;
    }
    usd[u][k]=0;
    return f[u][k];
}
void init(){
    memset(h,0,sizeof(h));
    memset(h2,0,sizeof(h2));
    scanf("%d%d%d%d",&n,&m,&K,&p);
    et=0;
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(h,u,v,w);
        add(h2,v,u,w);
    }
    dij2();
    memset(f,0,sizeof(f));
    memset(usd,0,sizeof(usd));
    printf("%d\n",dfs(1,K));
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}