[NOIP2017]逛公园

题目

题目描述

策策同学特别喜欢逛公园。公园可以看成一张$N$个点$M$条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，$N$号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从$N$号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点到$N$号点的最短路长为$d$，那么策策只会喜欢长度不超过$d + K$的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对$P$取模。

如果有无穷多条合法的路线，请输出$-1$。

输入输出格式

输入格式：

第一行包含一个整数 $T$, 代表数据组数。

接下来$T$组数据，对于每组数据：第一行包含四个整数 $N,M,K,P$，每两个整数之间用一个空格隔开。

接下来$M$行，每行三个整数$a_i,b_i,c_i$，代表编号为$a_i,b_i$的点之间有一条权值为 $c_i$的有向边，每两个整数之间用一个空格隔开。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

3
-1

说明

【样例解释1】

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

【测试数据与约定】

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

测试点编号	$T$	$N$	$M$	$K$	是否有0边
1	5	5	10	0	否
2	5	1000	2000	0	否
3	5	1000	2000	50	否
4	5	1000	2000	50	否
5	5	1000	2000	50	否
6	5	1000	2000	50	是
7	5	100000	200000	0	否
8	3	100000	200000	50	否
9	3	100000	200000	50	是
10	3	100000	200000	50	是

对于 100%的数据, $1 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 1000$。

数据保证：至少存在一条合法的路线。

题解

看到$k$很小就想到用$dp$了（大雾）

设$f_{u,j}$表示第$u$个点还有$j$个长度可以用来不走最短路

现在要从$u\rightarrow v$，设$u$的最短路为$d_u$，$v$的最短路为$d_v$，则走$u\rightarrow v$这条边需要格外长度为$d_v-(d_u+length_{u\rightarrow v})$

如果这个长度小于等于$j$，则可以转移

但是这样有个先后问题，因为这是个有向图

所以可以按$d$和拓扑序排序，然后进行转移

诶写个记忆化搜索就好了…靠近$N$的点先处理，最后答案就是$f_{1,k}$

只有存在$0$环才能输出$-1$的情况，所以搜索的时候判断当前情况是否存在在搜索栈中，在返回$-1$就行了

代码

# include<iostream>
# include<cstring>
# include<cstdlib>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=1e5+5;
struct p{
	int x,y,dis;
}c[MAX<<2],cc[MAX<<2];
struct q{
	int x,id;
}s[MAX<<2];
int T,n,m,k,P,num,Num;
int d[MAX],h[MAX],h1[MAX];
LL f[MAX][51];
bool use[MAX];
bool vis[MAX][51];
q min(q a,q b)
{
	return a.x<b.x?a:b;
}
void build(int l,int r,int k)
{
	s[k].x=1e9;
	if(l==r) s[k].id=l;
	if(l<r)
	{
		build(l,mid,tl),build(mid+1,r,tr);
		s[k]=min(s[tl],s[tr]);
	}
}
void change(int l,int r,int k,int x,int dis)
{
	if(l==r)
	{
		s[k].x=dis;
		return;
	}
	if(x<=mid) change(l,mid,tl,x,dis);
	else change(mid+1,r,tr,x,dis);
	s[k]=min(s[tl],s[tr]);
}
void Dijkstra()
{
	memset(d,1,sizeof(d));
	d[n]=0,change(1,n,1,n,0);
	while(1)
	{
		q tt=s[1];
		if(tt.x>1e8) break;
		change(1,n,1,tt.id,1e9);
		if(use[tt.id]) continue;
		use[tt.id]=1;
		for(int i=h[tt.id];i;i=c[i].x)
		  {
		  	int y=c[i].y;
		  	if(!use[y]&&d[y]>tt.x+c[i].dis) d[y]=tt.x+c[i].dis,change(1,n,1,y,d[y]);
		  }
	}
}
int dfs(int x,int t)
{
	if(vis[x][t]) return -1;
	if(f[x][t]) return f[x][t];
	vis[x][t]=1,f[x][t]=(x==n)?1:0;
	for(int i=h1[x];i;i=cc[i].x)
	  {
	  	int y=cc[i].y,tt=d[y]+cc[i].dis-d[x];
	  	if(tt<=t)
	  	{
	  		int T=dfs(y,t-tt);
  			if(T==-1) return -1;
			f[x][t]=(f[x][t]+T)%P;
		}
	  }
	return vis[x][t]=0,f[x][t];
}
int read()
{
	int x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void add(int x,int y,int dis)
{
	c[++num]=(p){h[x],y,dis},h[x]=num;
	cc[++Num]=(p){h1[y],x,dis},h1[y]=Num;
}
int main()
{
	T=read();
	while(T--)
	{
		n=read(),m=read(),k=read(),P=read(),num=Num=0;
		build(1,n,1);
		memset(use,0,sizeof(use));
		memset(vis,0,sizeof(vis));
		memset(h1,0,sizeof(h1));
		memset(h,0,sizeof(h));
		memset(f,0,sizeof(f));
		for(int i=1,x,y,dis;i<=m;++i)
		  x=read(),y=read(),dis=read(),add(y,x,dis);
		Dijkstra();
		printf("%d\n",dfs(1,k));
	}
	return 0;
}

题目