标签：SPFA，记忆化搜索
题目
题目描述
策策同学特别喜欢逛公园。公园可以看成一张\(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
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
输出样例#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\)。
数据保证：至少存在一条合法的路线。
分析
Attention：我的代码是假的，样例没法过，但能AC官方数据，挖坑待填！
设\(f[i][j]\)表示到\(i\)节点，还剩余\(j\)的值可以去绕路的方案数
\[ans=f[n][k]\]用SPFA处理最短路后
反向建图后记忆化搜索
假设在原图里有一条\(x->y \ cost=w\)的边，那么可以绕路的冗余长度为\(dix[x]+w-dis[y]\)
\[f[x][res]=\sum f[y][res-(dis[x]+w-dis[y]] （y->x）\]code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=2e5+6;
int T,n,m,K,mod,cnt=0,last[maxn],x[maxn],y[maxn],z[maxn];
int que[maxn<<2],dis[maxn],inque[maxn],f[maxn][56],in[maxn],re[maxn],flag;
struct edge{int to,next,w;}e[maxn<<1];
void insert(int u,int v,int val){e[++cnt]=(edge){v,last[u],val};last[u]=cnt;}
inline int dfs(int x,int res){
#define v e[i].to
if(~f[x][res])return f[x][res];
f[x][res]=(x==1);
// cout<<f[x][res]<<' '<<x<<' '<<res<<"R"<<endl;
reg(x){
int tmp=res-((dis[v]+e[i].w)-dis[x]);
// cout<<tmp<<' '<<in[v]<<' '<<re[v]<<endl;
if(tmp<0)continue;
if(in[v]&&re[v]==tmp)flag=1;else in[v]=1,re[v]=tmp;
// cout<<tmp<<' '<<in[v]<<' '<<re[v]<<endl;
f[x][res]=(f[x][res]+dfs(v,tmp))%mod;
// cout<<f[x][res]<<' '<<dfs(v,tmp)<<endl;
in[v]=0,re[v]=0;
}
return f[x][res];
}
void work(){
mem(last,0);cnt=0;mem(que,0);mem(inque,0);mem(dis,inf);
n=read(),m=read(),K=read(),mod=read();
rep(i,1,m){
x[i]=read(),y[i]=read(),z[i]=read();
insert(x[i],y[i],z[i]);
}
int head=0,tail=1;que[head]=1;dis[1]=0;inque[1]=1;
while(head<tail){
int now=que[head++];
reg(now)
if(dis[v]>dis[now]+e[i].w){
dis[v]=dis[now]+e[i].w;
if(!inque[v])inque[v]=1,que[tail++]=v;
}
inque[now]=0;
}
mem(last,0);cnt=0;mem(f,-1);flag=0;
rep(i,1,m)insert(y[i],x[i],z[i]);
int tmp=dfs(n,K);
printf("%d\n",flag?-1:tmp);
}
int main()
{
T=read();
rep(i,1,T)work();
return 0;
}
