代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
using namespace std;
char ch[29999999],*it=ch;
void in(int&x){
	for(x=0;*it<'0'||*it>'9';++it);
	for(;x=x*10+*it-48,*++it>='0'&&*it<='9';);
}
const int N=100009,M=200009;
int n,m,K,p,d[N],g[N][55];
int ne[M],to[M],len[M],he[N];
int ner[M],tor[M],her[N];
bool f[N],b[N][55],s[N][55],er;
priority_queue<pair<int,int> >Q;
void dfs(const int&x,const int&y){
	if(s[x][y]){
		er=1;
		return;
	}
	if(b[x][y])return;
	s[x][y]=1;
	if(x==1&&y==0)g[x][y]=1;
	register int i,j,k;
	for(j=her[x];j;j=ner[j]){
		if(er)return;
		i=tor[j],k=d[x]+y-len[j]-d[i];
		if(k>=0)dfs(i,k),g[x][y]=(g[x][y]+g[i][k])%p;
	}
	b[x][y]=1,s[x][y]=0;
}
int main(){
	fread(ch,1,29999991,stdin);
	register int T,i,j,k,l,t,a;
	in(T);
	while(T--){
		in(n),in(m),in(K),in(p);
		memset(he,0,sizeof(he)),memset(her,0,sizeof(her));
		memset(f,0,sizeof(f)),er=t=a=0;
		while(m--){
			in(i),in(j),in(k);
			ne[++t]=he[i],to[t]=j,len[t]=k,he[i]=t;
			ner[t]=her[j],tor[t]=i,her[j]=t;
		}
		memset(d,63,sizeof(d)),d[1]=0,Q.push(make_pair(0,1));
		while(!Q.empty()){
			i=Q.top().second,Q.pop();
			if(f[i])continue;
			f[i]=1;
			for(j=he[i];j;j=ne[j]){
				k=to[j];
				if(f[k])continue;
				l=d[i]+len[j];
				if(d[k]>l)d[k]=l,Q.push(make_pair(-l,k));
			}
		}
		memset(s,0,sizeof(s)),memset(g,0,sizeof(g)),memset(b,0,sizeof(b));
		for(i=K;i>=0;--i){
			if(er)break;
			dfs(n,i),a=(a+g[n][i])%p;
		}
		if(er)puts("-1");
		else printf("%d\n",a);
	}
}

评测结果