逛公园

P3953 逛公园

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

用拓扑啊什么的一想就很麻烦。

有一种玄学的做法：记忆化搜索

(f[x][k])表示(dis(x,n)<=MinDis(x,n)+k)的路径数。

先跑一般反向的最短路，然后dfs

考虑边((x,y,w)),

(ecause Mindis[x]-Mindis[y]+w<k​)

( herefore f[x][k]+=f[y][k-(Mindis[x]-Mindis[y]+w)])

( herefore f[x][k] = sum f[y][k-(Mindis[x]-Mindis[y]+w)])

#include<cstdio>
#include<cstring>
#include<queue>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define gc getchar
int gi(){int x=0,f=0;char c=gc();while(c<'0'||'9'<c){if(c=='-')f=!f;c=gc();}while('0'<=c&&c<='9'){x=x*10+c-48;c=gc();}return f?(-x):x;}
using namespace std;
#define N 100010
#define fl(head,i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
int n,m,cnt,k,mod,f[N][51],h1[N],h2[N],d[N];
bool is[N][51],v[N];
struct eg{int to,w,nxt;}e[N*4];
void add(int x,int y,int w,int *head){e[++cnt]=(eg){y,w,head[x]};head[x]=cnt;}
struct cmp{bool operator()(int a,int b){return d[a]>d[b];}};
priority_queue<int,vector<int>,cmp>q;
void spfa(){
    clr(d,126);
    int x;d[n]=0;q.push(n);
    while(!q.empty()){
        x=q.top();q.pop();v[x]=0;
        fl(h2,i,x)
        if(d[x]+e[i].w<d[to]){
            d[to]=d[x]+e[i].w;
            if(!v[to])q.push(to),v[to]=1;
        }
    }
}
int dfs(int x,int k){
    if(is[x][k])return -1;
    if(f[x][k])return f[x][k];
    is[x][k]=1;f[x][k]=(x==n);
    int tmp,w;
    fl(h1,i,x)
    if((tmp=d[to]-d[x]+e[i].w)<=k)
        if((w=dfs(to,k-tmp))){
            if(w==-1)return w;
            f[x][k]+=w;if(f[x][k]>mod)f[x][k]-=mod;
        }
    is[x][k]=0;
    return f[x][k];
}
int main(){
int T=gi(),x,y,w;
while(T--){
    n=gi();m=gi();k=gi();mod=gi();cnt=0;
    clr(f,0);clr(h1,0);clr(h2,0);clr(is,0);
    Fur(i,1,m)x=gi(),y=gi(),w=gi(),add(x,y,w,h1),add(y,x,w,h2);
    spfa();printf("%d
",dfs(1,k));
}
}