难道有人看题解不点赞的吗？

题目解析

• 首先看到题目中写：“如果 $1$ 号点 到 $N$ 号点的最短路长为 $d$，那么策策只会喜欢长度不超过 $d + K$ 的路线”。
  所以，很明显，我们要跑一遍 Dijkstra 算法。
• 接下来我们使用记忆化搜索。
  设 $dp_{u,k}$ 为从 $1$ 号点进去，从 $u$ 号点出来，且花至多 $dis_u+k$ 的时间，总共有多少条满足条件的路线。$dp$ 初始值为 $-1$。$dp_{1,k}=1$。
• 遍历 $u$ 的邻点 $v$，设 $dp_{u,k}$ 由 $dp_{v,k'}$ 转移得到，则

• 不过还有个问题，就是什么时候输出 $-1$。
  发现这时会出现“零环”，所以我们要开一个 $instk$ 数组，如果回溯前两次遍历到同一个状态便出现了“零环”。

呼，该讲的都讲完了，接下来是——

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const ll N=1e5+10;
priority_queue<PLL,vector<PLL>,greater<PLL>> q;
vector<pair<ll,ll>> e[N],e2[N];
ll t,n,m,K,p,dis[N],dp[N][55];
bool flg,vis[N],instk[N][55];
ll dfs(ll u,ll k) {
	if(instk[u][k]==1) return -1;
	if(~dp[u][k]) return dp[u][k];
	instk[u][k]=1,dp[u][k]=(u==1);
	for(auto x:e2[u]) {
		ll v=x.first,w=x.second,nk=dis[u]-dis[v]+k-w;
		if(nk<0 || nk>K) continue;
		if(dfs(v,nk)==-1) return -1;
		dp[u][k]=(dp[u][k]+dp[v][nk])%p;
	}
	instk[u][k]=0;
	return dp[u][k];
}
int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--) {
		cin>>n>>m>>K>>p;
		for(ll i=1; i<=n; ++i) e[i].clear(),e2[i].clear();
		for(ll i=1,a,b,c; i<=m; ++i) cin>>a>>b>>c,e[a].push_back({b,c}),e2[b].push_back({a,c});
		for(ll i=1; i<=n; ++i) dis[i]=9e18,vis[i]=0;
		dis[1]=0,q=priority_queue<PLL,vector<PLL>,greater<PLL>>(),q.push({0,1});
		while(!q.empty()) {
			ll u=q.top().second;
			q.pop();
			if(vis[u]) continue;
			vis[u]=1;
			for(auto x:e[u]) {
				ll v=x.first,w=x.second;
				if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,q.push({dis[v],v});
			}
		}
		for(ll i=1; i<=n; ++i) for(ll j=0; j<=K; ++j) dp[i][j]=-1,instk[i][j]=0;
		flg=0,cout<<dfs(n,K)<<"\n";
	}
	return 0;
}

完结撒花~~