记录编号	475826	评测结果	AAAAAAAAAA
题目名称	[NOIP 2017]逛公园	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	4.227 s
提交时间	2017-11-18 19:41:50	内存使用	20.84 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100005,maxm=200005;
struct A{
	int x,d;
	A(int x,int d):x(x),d(d){}
	bool operator<(const A &a)const{return d>a.d;}
};
void Dijkstra(int);
void bfs();
vector<int>G[maxn],W[maxn],G2[maxn],RG2[maxn];
bool vis[maxn];
int d[maxn],dis[maxn],du[maxn],q[maxn],u[maxm],v[maxm],w[maxm];
int T,n,m,k,p,f[maxn][55],head,tail;
int main(){
	freopen("2017park.in","r",stdin);
	freopen("2017park.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		memset(du,0,sizeof(du));
		memset(f,0,sizeof(f));
		scanf("%d%d%d%d",&n,&m,&k,&p);
		for(int i=1;i<=n;i++){
			G[i].clear();
			W[i].clear();
			G2[i].clear();
			RG2[i].clear();
		}
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&u[i],&v[i],&w[i]);
			G[v[i]].push_back(u[i]);
			W[v[i]].push_back(w[i]);
		}
		Dijkstra(n);
		memcpy(d,dis,sizeof(d));
		for(int i=1;i<=n;i++){
			G[i].clear();
			W[i].clear();
		}
		for(int i=1;i<=m;i++){
			G[u[i]].push_back(v[i]);
			W[u[i]].push_back(w[i]);
		}
		Dijkstra(1);
		for(int i=1;i<=m;i++)if(d[u[i]]==d[v[i]]+w[i]){
			//printf("(%d,%d) w=%d\n",u[i],v[i],w[i]);
			G2[u[i]].push_back(v[i]);
			RG2[v[i]].push_back(u[i]);
			du[u[i]]++;
		}
		bfs();
		bool bad=false;
		for(int i=1;i<=n;i++)if(!vis[i]&&d[i]+dis[i]<=d[1]+k){
			bad=true;
			break;
		}
		if(bad){
			printf("-1\n");
			continue;
		}
		//for(int i=1;i<=n;i++)if(!vis[i])printf("d[%d]=%d dis[%d]=%d D=%d k=%d\n",i,d[i],i,dis[i],d[1],k);
		f[n][0]=1;
		for(int j=0;j<=k;j++){
			if(j){
				for(int x=1;x<=n;x++)if(vis[x])for(int i=0;i<(int)G[x].size();i++){
					int t=d[x]-d[G[x][i]]+j-W[x][i];//printf("%d %d t=%d\n",x,G[x][i],t);
					if(t>=0&&t<j){
						f[x][j]=f[x][j]+f[G[x][i]][t];
						if(f[x][j]>=p)f[x][j]-=p;
					}
				}
			}
			for(int i=0;i<tail;i++){
				int x=q[i];
				for(int t=0;t<(int)G2[x].size();t++){
					f[x][j]=f[x][j]+f[G2[x][t]][j];
					if(f[x][j]>=p)f[x][j]-=p;
				}
			}
			//for(int i=1;i<=n;i++)printf("f[%d][%d]=%d\n",i,j,f[i][j]);
		}
		int ans=0;
		for(int i=0;i<=k;i++){
			ans+=f[1][i];
			if(ans>=p)ans-=p;
		}
		printf("%d\n",ans);
	}
	return 0;
}
void Dijkstra(int x){
	memset(dis,63,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<A>heap;
	dis[x]=0;
	heap.push(A(x,0));
	while(!heap.empty()){
		x=heap.top().x;
		heap.pop();
		vis[x]=true;
		for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&dis[G[x][i]]>dis[x]+W[x][i]){
			dis[G[x][i]]=dis[x]+W[x][i];
			heap.push(A(G[x][i],dis[G[x][i]]));
		}
	}
}
void bfs(){
	head=tail=0;
	for(int i=1;i<=n;i++)if(!du[i])q[tail++]=i;
	memset(vis,0,sizeof(vis));
	while(head!=tail){
		int x=q[head++];//printf("%d ",x);
		vis[x]=true;
		for(int i=0;i<(int)RG2[x].size();i++)if(!--du[RG2[x][i]])q[tail++]=RG2[x][i];
	}
	//printf("\n");
}