代码

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;
typedef std::pair<int, int> pii;

template<typename T>
void read(T &x) {
    int flag = 1; x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
#if __cplusplus >= 201103l
template<typename T, typename... V>
void read(T &x, V&... v) { read(x), read(v...); }
#endif

const int N = 1e5 + 10, M = 2e5 + 10;
int cnt, from[N], to[M], nxt[M], dis[M];
struct Edge { int u, v, w; } d[M];
int T, n, m, k, p, f[100][N], dist[N];
inline void addEdge(int u, int v, int w) {
	to[++cnt] = v, nxt[cnt] = from[u], from[u] = cnt, dis[cnt] = w;
}
std::priority_queue<pii, std::vector<pii>, std::greater<pii>> Q;

void doit(int s) {
	memset(dist, 127, sizeof (dist[0]) * (n + 1));
	dist[s] = 0; Q.push({0, s});
	while(Q.size()) {
		pii u = Q.top(); Q.pop();
		if(u.first != dist[u.second]) continue;
		for(int i = from[u.second]; i; i = nxt[i]) {
			int v = to[i], w = dist[u.second] + dis[i];
			if(w < dist[v]) Q.push({dist[v] = w, v});
		}
	}
}

bool g[100][N], flag;
int dp(int k, int u) {
	if(k < 0) return 0;
	if(g[k][u]) { flag = 1; return 0; }
	if(~f[k][u]) return f[k][u];
	int &now = f[k][u]; now = 0; g[k][u] = 1;
	for(int i = from[u]; i; i = nxt[i]) {
		int v = to[i], w = dist[u] + k - dis[i];
		if(w - dist[v] > k) continue;
		(now += dp(w - dist[v], v)) %= p;
	}
	if(k == 0 && u == 1) now = 1;
	return g[k][u] = 0, now;
}

int main() {
	read(T);
	for(int Case = 1; Case <= T; ++Case) {
		read(n, m, k, p), flag = 0;
		cnt = 0, memset(from, 0, sizeof(from[0]) * (n + 1));
		for(int i = 1; i <= m; ++i)
			read(d[i].u, d[i].v, d[i].w), addEdge(d[i].u, d[i].v, d[i].w);
		for(int i = 0; i <= k; ++i)
			memset(f[i], -1, sizeof (f[i][0]) * (n + 1));
		doit(1);
		cnt = 0, memset(from, 0, sizeof(from[0]) * (n + 1));
		for(int i = 1; i <= m; ++i) addEdge(d[i].v, d[i].u, d[i].w);
		int ret = 0;
		for(int i = 0; i <= k; ++i) (ret += dp(i, n)) %= p;
		printf("%d\n", flag ? -1 : ret);
	}
    return 0;
}

评测结果