Description
给出一张n个点m条边的有向图，边权为非负整数。求满足路径长度小于等于1到n最短路+k的1到n的路径条数模p，如果有无数条则输出−1。
Input
第一行包含一个整数T,代表数据组数。
接下来T组数据，对于每组数据：第一行包含四个整数N,M,K,P，每两个整数之间用一个空格隔开。
接下来M行，每行三个整数ai,bi,ci，代表编号为ai,bi的点之间有一条权值为ci的有向边，每两个整数之间用一个空格隔开。
Output
输出文件包含T行，每行一个整数表示答案。
Sample Input
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
Sample Output
3
-1
首先求单源最短路，然后设(f[i][k])表示当前到i号点，所经过的路程比最短路多了k。那么转移显然为(f[x][dis[son]-dis[x]+v-val[p]]Rightarrow f[son][v])，因此这个转移肯定是枚举反向边进行转移。然后我们可以对(f)进行记搜，这样便可以省略拓扑判零环。
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=1e5,M=2e5;
int n,m,K,MOD,Ans;
struct Link{
int pre[M+10],now[N+10],child[M+10],val[M+10],tot;
void init(){tot=0,memset(now,0,sizeof(now));}
void insert(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}
}Frw,Bck;//Forward,Back
int h[N+10],dis[N+10],f[N+10][55];
bool vis[N+10],can[N+10][55],flag;
void SPFA(int x){
int head=0,tail=1;
memset(dis,63,sizeof(dis));
h[1]=x,dis[x]=0,vis[x]=1;
while (head!=tail){
if (++head>N) head=1;
int Now=h[head];
for (int p=Frw.now[Now],son=Frw.child[p];p;p=Frw.pre[p],son=Frw.child[p]){
if (dis[son]>dis[Now]+Frw.val[p]){
dis[son]=dis[Now]+Frw.val[p];
if (!vis[son]){
if (++tail>N) tail=1;
vis[h[tail]=son]=1;
}
}
}
vis[Now]=0;
}
}
int dfs(int x,int v){
if (~f[x][v]) return f[x][v];
can[x][v]=1,f[x][v]=(x==1&&!v)?1:0;
//到了(1,0)不要立刻停止，因为有可能出现全图都是0边的情况，直接退出就会挂
for (int p=Bck.now[x],son=Bck.child[p];p;p=Bck.pre[p],son=Bck.child[p]){
int tmp=dis[x]+v-dis[son]-Bck.val[p];
if (tmp>=0){
if (can[son][tmp]) flag=1;
f[x][v]=(f[x][v]+dfs(son,tmp))%MOD;
}
}
can[x][v]=0;
return f[x][v];
}
void init(){
flag=0,Ans=0;
Frw.init(),Bck.init();
memset(f,255,sizeof(f));
n=read(),m=read(),K=read(),MOD=read();
}
int main(){
for (int Data=read();Data;Data--){
init();
for (int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
Frw.insert(x,y,z);
Bck.insert(y,x,z);
}
SPFA(1);
for (int i=0;i<=K;i++) Ans=(Ans+dfs(n,i))%MOD;
printf("%d
",flag?-1:Ans);
}
return 0;
}