[luogu3952 noip2017] 逛公园 (计数dp+最短路)

传送门

Description

Input

Output

输出文件包含 T 行，每行一个整数代表答案。

Sample Input

2

5 7 2 10

1 2 1

2 4 0

4 5 2

2 3 2

3 4 1

3 5 2

1 5 3

2 2 0 10

1 2 0

2 1 0

Sample Output

3

-1

HINT

【样例解释1】

对于第一组数据，最短路为 3 。 \(1 – 5\), \(1 – 2 – 4 – 5\),\(1 – 2 – 3 – 5\) 为 3 条合法路径。

【测试数据与约定】

对于不同的测试点，我们约定各种参数的规模不会超过如下

Solution

设dis[i]为i到n最短路

设dp[i][j]表示dis<=dis[i]+j的i到n的方案数

转移时把所有符合条件的都转移过来，如果发现某个dp同时出现说明有0环直接输出-1

用记搜很好实现

Code

最终还是最短路写错了(Ｔ▽Ｔ)

//By Menteur_Hxy

#include <queue>

#include <cstdio>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define M(a,b) memset(a,(b),sizeof(a))

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

#define _E(i,u) for(register int i=_head[u];i;i=_nxt[i])

#define E(i,u) for(register int i=head[u];i;i=nxt[i])

using namespace std;

typedef pair<int,int> PII;

int read() {

	int x=0,f=1; char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=100010,M=200010;

int n,m,K,MOD,cnt,_cnt;

int dis[N],nxt[M],_nxt[M],to[M],_to[M],w[M],_w[M],head[N],_head[N],vis[N],dp[N][60],in[N][60];

vector <int> V[N];

void dij() {

	priority_queue<PII,vector<PII>,greater<PII> > Q;

	Q.push(PII(dis[n]=0,n));

	while(!Q.empty()) {

		int u=Q.top().second,v; Q.pop();

		if(vis[u]) continue; vis[u]=1;

		E(i,u) if(dis[v=to[i]]>dis[u]+w[i]) {

			dis[v]=dis[u]+w[i];

			Q.push(PII(dis[v],v));

		}

	}

}

int dfs(int u,int k) {

	if(in[u][k]) return -1;

	if(dp[u][k]) return dp[u][k];

	in[u][k]=1; dp[u][k]=(u==n);

	int tmp,v,reg;

	_E(i,u) if((tmp=dis[v=_to[i]]+_w[i]-dis[u])<=k) {

		if((reg=dfs(v,k-tmp))==-1) return dp[u][k]=-1;

		dp[u][k]=(dp[u][k]+reg)%MOD;

	}

	return in[u][k]=0,dp[u][k];

}

#define _add(a,b,c) _nxt[++_cnt]=_head[a],_to[_cnt]=b,_w[cnt]=c,_head[a]=_cnt

#define add(a,b,c) nxt[++cnt]=head[a],to[cnt]=b,w[cnt]=c,head[a]=cnt

int main() {

	int T=read();

	while(T--) {

		_cnt=cnt=0;M(dis,0x3f);M(head,0);M(vis,0);M(dp,0),M(in,0),M(_head,0);

		n=read(),m=read(),K=read(),MOD=read();

		F(i,1,n) V[i].clear();

		F(i,1,m) {

			int a=read(),b=read(),c=read();

			add(b,a,c); _add(a,b,c);

		}

		dij();

		printf("%d\n",dfs(1,K));

	}

	return 0;

}