题面
题目描述
策策同学特别喜欢逛公园。公园可以看成一张 \(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\) 行，每行一个整数代表答案。
输入输出样例
输入样例：
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
输出样例：
3
-1
说明
【样例解释1】
对于第一组数据，最短路为 \(3\) 。 \(1 - 5, 1 - 2 - 4 - 5, 1 - 2 - 3 - 5\) 为 \(3\) 条合法路径。
【测试数据与约定】
对于不同的测试点，我们约定各种参数的规模不会超过如下
| \(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\) 。
数据保证：至少存在一条合法的路线。
思路
\(NOIP2017 / DAY1 / T3\)
首先我们求出每个点到 \(n\) 结点（公园出口）的距离，然后定义一个变量 \(dp[i][j]\) 表示比从 \(i\) 点出发到达 \(n\) 点的最短路长小于等于 \(j\) 的路径有多少条。然后我们逐步向后遍历整张图，求出的 \(dp[1][K]\) 就是题目要求的答案。遍历过程中我们可以用记忆化搜索的形式来优化时间复杂度。
那怎么判断无数多条合法情况呢？再定义一个变量 \(in[i][j]\) 表示在当前遍历过程中我们是否有在求 \(dp[i][j]\) 。如果有，说明搜索成环，直接返回 \(-1\) 。
具体实现代码如下：
LL dfs(LL now,LL k)
{
if(in[now][k]) return -1;//成环
if(dp[now][k]) return dp[now][k];//记忆化搜索
in[now][k]=true,dp[now][k]=0;//开始搜索
if(now==n) dp[now][k]=1;//搜到结尾时为一种情况
for(LL i=top[now];i;i=nex[i])
{
LL delta=dis[to[i]]-dis[now]+len[i];//与最短路之间的差距
if(delta<=k)
{
LL tmp=dfs(to[i],k-delta);
if(tmp==-1) return -1;//成环
dp[now][k]=(dp[now][k]+tmp)%p;
}
}
in[now][k]=false;//结束搜索
return dp[now][k];
}
函数调用入口就是：
printf("%lld\n",dfs(1,K));
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN=100005;
LL T,n,m,K,p,dp[MAXN][55],dis[MAXN];
LL cnt,top[MAXN],to[MAXN<<1],len[MAXN<<1],nex[MAXN<<1];
LL __cnt,__top[MAXN],__to[MAXN<<1],__len[MAXN<<1],__nex[MAXN<<1];
bool vis[MAXN],in[MAXN][55];
LL read()
{
LL re=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return re;
}
void SPFA()
{
memset(dis,0x3f,sizeof dis);
memset(vis,false,sizeof vis);
dis[n]=0;
queue<LL>Q;
Q.push(n);
while(!Q.empty())
{
LL now=Q.front();Q.pop();
vis[now]=false;
for(LL i=__top[now];i;i=__nex[i])
if(dis[__to[i]]>dis[now]+__len[i])
{
dis[__to[i]]=dis[now]+__len[i];
if(!vis[__to[i]])
{
vis[__to[i]]=true;
Q.push(__to[i]);
}
}
}
}
LL dfs(LL now,LL k)
{
if(in[now][k]) return -1;
if(dp[now][k]) return dp[now][k];
in[now][k]=true,dp[now][k]=0;
if(now==n) dp[now][k]=1;
for(LL i=top[now];i;i=nex[i])
{
LL delta=dis[to[i]]-dis[now]+len[i];
if(delta<=k)
{
LL tmp=dfs(to[i],k-delta);
if(tmp==-1) return -1;
dp[now][k]=(dp[now][k]+tmp)%p;
}
}
in[now][k]=false;
return dp[now][k];
}
int main()
{
T=read();
while(T--)
{
n=read(),m=read(),K=read(),p=read(),cnt=__cnt=0;
memset(dp,0,sizeof dp);
memset(top,0,sizeof top);
memset(__top,0,sizeof __top);
memset(in,false,sizeof in);
while(m--)
{
LL x=read(),y=read(),z=read();
to[++cnt]=y,len[cnt]=z,nex[cnt]=top[x],top[x]=cnt;
__to[++__cnt]=x,__len[__cnt]=z,__nex[__cnt]=__top[y],__top[y]=__cnt;
}
SPFA();
printf("%lld\n",dfs(1,K));
}
return 0;
}