自动搬运

查看原文

来自洛谷，原作者为

	JayJessy RP++

搬运于2025-08-24 21:54:32，当前版本为作者最后更新于2024-07-09 20:36:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

第一眼紫题，便有了退缩之意，但这是必做题，于是我默默地点开了题解……然后就发现其实思路不是哪么难（代码调了两个小时）。

题目解析

• 首先看到题目中写：“如果 $1$ 号点 到 $N$ 号点的最短路长为 $d$，那么策策只会喜欢长度不超过 $d + K$ 的路线”。
  所以，很明显，我们要跑一遍 Dijkstra 算法。

void dij() {
	memset(vis1,0,sizeof(vis1));
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	q.push({0,1});
	while(!q.empty()) {
		ll u=q.top().second;
		q.pop();
		if(vis1[u]) continue;
		vis1[u]=1;
		for(auto x:e1[u]) {
			ll v=x.first,w=x.second;
			if(d[v]>d[u]+w) d[v]=d[u]+w,q.push({d[v],v});
		}
	}
}

• 接下来我们使用记忆化搜索。
  设 $dp_{u,k}$ 为从 $1$ 号点进去，从 $u$ 号点出来，且花恰好 $d[u]+k$ 的时间，总共有多少条满足条件的路线。$dp$ 初始值为 $-1$。
  遍历 $u$ 的邻点 $v$，设 $dp_{u,k}$ 由 $dp_{v,k'}$ 转移得到，则
  $d_u+k=d_v+k'+w(u,v)$
  $k'=d_u-d_v+k-w(u,v)$
  $dp$ 数组的初值是 $dp_{1,0}=1$。
  不过还有个问题，就是什么时候输出 $-1$。
  发现这时会出现“零环”，所以我们要开一个 $vis$ 数组，如果两次遍历到同一个点便出现了“零环”。

ll dfs(ll u,ll k) {
	if(vis2[u][k]) {
		flg=1;
		return 0;
	}
	if(~dp[u][k]) return dp[u][k];
	vis2[u][k]=1;
	dp[u][k]=0;
	for(auto x:e2[u]) {
		ll v=x.first,w=x.second,nk=d[u]-d[v]+k-w;
		if(nk<0 || nk>K) continue;
		dp[u][k]=(dp[u][k]+dfs(v,nk))%p;
		if(flg) {
			vis2[u][k]=0;
			return 0;
		}
	}
	if(u==1 && k==0) dp[u][k]=1;
	vis2[u][k]=0;
	return dp[u][k];
}

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

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<PLL> e1[N],e2[N];
ll t,n,m,K,p,d[N],dp[N][60];
bool flg,vis1[N],vis2[N][60];
void dij() {
	memset(vis1,0,sizeof(vis1));
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	q.push({0,1});
	while(!q.empty()) {
		ll u=q.top().second;
		q.pop();
		if(vis1[u]) continue;
		vis1[u]=1;
		for(auto x:e1[u]) {
			ll v=x.first,w=x.second;
			if(d[v]>d[u]+w) d[v]=d[u]+w,q.push({d[v],v});
		}
	}
}
ll dfs(ll u,ll k) {
	if(vis2[u][k]) {
		flg=1;
		return 0;
	}
	if(~dp[u][k]) return dp[u][k];
	vis2[u][k]=1;
	dp[u][k]=0;
	for(auto x:e2[u]) {
		ll v=x.first,w=x.second,nk=d[u]-d[v]+k-w;
		if(nk<0 || nk>K) continue;
		dp[u][k]=(dp[u][k]+dfs(v,nk))%p;
		if(flg) {
			vis2[u][k]=0;
			return 0;
		}
	}
	if(u==1 && k==0) dp[u][k]=1;
	vis2[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++) e1[i].clear(),e2[i].clear();
		for(ll i=1,a,b,c; i<=m; i++) {
			cin>>a>>b>>c;
			e1[a].push_back({b,c});
			e2[b].push_back({a,c});
		}
		dij();
		flg=0;
		memset(dp,-1,sizeof(dp));
		ll ans=0;
		for(ll i=0; i<=K; i++) {
			ans=(ans+dfs(n,i))%p;
			if(flg) break;
		}
		if(flg) cout<<"-1\n";
		else cout<<ans<<"\n";
	}
	return 0;
}

完结撒花~~