代码

#include <bits/stdc++.h>

using namespace std;
namespace DEBUG {
	void debug_out() { cerr << '\n'; }
	template <typename Head, typename... Tail>
	void debug_out(Head H, Tail... T) { cerr << ' ' << H, debug_out(T...); }
	#define debug(...) cerr << '[' << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
} using namespace DEBUG;
namespace fastIO {
	#define getchar() (S == T && (T = (S = B) + fread(B, 1, 1 << 16, stdin), S == T) ? EOF : *S++)
	char B[1 << 16], *S = B, *T = B;
	template<typename Tp> inline void read(Tp &o) {
		Tp x = 0; bool  s = 0; char c = getchar();
		while(c > '9' || c < '0') s |= (c == '-'), c = getchar();
		while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		o = s ? -x : x;
	}
} using fastIO::read;
const int N = 1e5 + 5, M = 2e5 + 5;
int T, n, m, K, ind[N], MD;
struct edge { int v, w; };
vector<edge> g[N], ig[N], g0[N];
vector<int> d1, dn;

vector<int> dijkstra(int s, vector<edge> G[]) {
	vector<int> d(n + 1, 1e9), vis(n + 1, 0);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	d[s] = 0, q.push(make_pair(0, s));
	while(q.size()) {
		int u = q.top().second;
		q.pop();
		if(vis[u]++) continue;
		for(edge &e : G[u])
			if(d[u] + e.w < d[e.v]) q.push(make_pair(d[e.v] = d[u] + e.w, e.v));
	}
	return d;
}

bool topo() {
	for(int i = 1; i <= n; i++) for(edge &e : g[i]) 
		if(e.w == 0) g0[i].emplace_back(edge{e.v, 0}), ++ind[e.v];
	queue<int> q;
	for(int i = 1; i <= n; i++) if(!ind[i]) q.push(i);
	while(q.size()) {
		int u = q.front(); q.pop();
		for(edge &e : g0[u]) if(--ind[e.v] == 0) q.push(e.v);
	}
	for(int i = 1; i <= n; i++)
		if(ind[i] != 0) for(edge &e : g0[i])
				if(d1[i] + dn[e.v] <= d1[n] + K) return true;
	return false;
}

int s[N][55];
int dp(int u, int j) {
	if(s[u][j] != -1) return s[u][j];
	s[u][j] = 0;
	for(edge &e : ig[u]) {
		int v = e.v, k = d1[u] + j - e.w - d1[v];
		if(k >= 0 && k <= K) s[u][j] = (s[u][j] + dp(v, k)) % MD;
	}
	return s[u][j];
}

void clear() {
	for(int i = 1; i <= n; i++) g[i].clear(), ig[i].clear(), g0[i].clear();
	for(int i = 1; i <= n; i++) ind[i] = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= K; j++) s[i][j] = -1;
}

int main() {
	for(read(T); T; T--) {
		read(n), read(m), read(K), read(MD);
		clear();
		for(int i = 1, u, v, w; i <= m; i++) {
			read(u), read(v), read(w);
			g[u].emplace_back(edge{v, w}), ig[v].emplace_back(edge{u, w});
		}
		d1 = dijkstra(1, g), dn = dijkstra(n, ig);
		if(topo()) {
			cout << -1 << '\n';
			continue;
		}
		s[1][0] = 1;
		int ans = 0;
		for(int i = 0; i <= K; i++)
			ans = (ans + dp(n, i)) % MD;
		cout << ans << '\n';
	}

	return 0;
}

评测结果