luoguP3953 逛公园

很经典（😏）的一道题，发现k不是很大，可以枚举k，然后跑一个记忆化搜索统计答案
思路简单，但是写起来有些难度

可以dp来做，用f[i][j]表示从n到i的距离<最短距离+k的方案数，对于每一条边都尝试走，而这个状态可以表示为u->v: d[u]-d[v]+k-len[u->v];最后西格玛一下就over了
挺神奇的哈

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > v1[1100000],v2[1100000];
inline int read(){
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9'){
		if(c=='-')
			flag=1;
		c=getchar();
	}
    while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
    return flag?-x:x;
}
int dis[1100000],n,m;
void spfa(int s){
	for(int i=1;i<=n;i++){
		dis[i]=2147483646;
	}
	queue<int> q;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<v1[now].size();i++){
			int v=v1[now][i].first,w=v1[now][i].second;
			if(dis[v]>dis[now]+w){
				dis[v]=dis[now]+w;
				q.push(v); 
			}
		}
	}
}
int k,dp[100100][55],mod;
bool vis[100100][55];
int dfs(int x,int left){
	if(left<0||left>k)return 0;
	int ans=0;
	if(vis[x][left]){
		vis[x][left]=0;
		return -1;
	}
	if(dp[x][left]!=-1)return dp[x][left];
	vis[x][left]=1;
	for(int i=0;i<v2[x].size();i++){
        int sum=dfs(v2[x][i].first,dis[x]+left-dis[v2[x][i].first]-v2[x][i].second);
	    if(sum==-1){
            vis[x][left]=0;
            return -1;
        }
        ans=(ans+sum)%mod;
	}
	vis[x][left]=0;
    if(x==1&&left==0)ans++;
    dp[x][left]=ans;
    return ans;
}
int main(){
	ios::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--){
		//n=read();
		//m=read();
		//k=read();
		//mod=read();
		cin>>n>>m>>k>>mod;
		for(int i=1;i<=n;i++){
			v1[i].clear();
			v2[i].clear();
		}
		for(int i=1;i<=m;i++){
			int u,v,w;
		//	u=read();
		//	v=read();
		//	w=read();
			cin>>u>>v>>w;
			v1[u].push_back(make_pair(v,w));
			v2[v].push_back(make_pair(u,w));
		} 
		spfa(1);
		memset(dp,-1,sizeof(dp));
		int ans=0;
		for(int i=0;i<=k;i++){
			int tmp=dfs(n,i);
			if(tmp==-1){
				ans=-1;
				break;
			}
			ans=(ans+tmp)%mod; 
		}
		cout<<ans<<endl;
	}
	return 0;
}