1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
struct Edge {int v, w;};
vector<Edge> G1[MAXN], G2[MAXN];
int T, N, M, K, P;
bool fail;
int f[MAXN][51];
int d[MAXN];
bool vis[MAXN];
bool ins[MAXN][51];
void Dijkstra() {
memset(vis, 0, sizeof(vis));
memset(d, 0x3f, sizeof(d));
priority_queue<pair<int, int> > q;
q.push(make_pair(0, 1));
d[1] = 0;
while (q.size()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (vector<Edge>::iterator it = G1[u].begin(); it != G1[u].end(); it++) {
int v = it->v, w = it->w;
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
q.push(make_pair(-d[v], v));
}
}
}
}
inline int dp(int u, int k) {
if (k < 0) return 0;
if (ins[u][k]){
fail = 1;
return 0;
}
if (f[u][k]) return f[u][k];
ins[u][k] = 1;
int ans = 0;
for (vector<Edge>::iterator it = G2[u].begin(); it != G2[u].end(); it++) {
int p = it->v, w = it->w;
ans = (ans + dp(p, d[u] - d[p] + k - w))%P;
if (fail == 1) return 0;
}
ins[u][k] = 0;
return f[u][k] = ans;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d", &N, &M, &K, &P);
for (register int i = 1; i <= M; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G1[u].push_back((Edge){v, w});
G2[v].push_back((Edge){u, w});
}
Dijkstra();
dp(1, 0);
f[1][0] = 1;
int ans = 0;
for (register int i = 0; i <= K; ++i) {
ans = (ans + dp(N, i))%P;
}
if(fail == 1) puts("-1");
else printf("%d\n", ans);
fail = 0;
memset(f, 0, sizeof(f));
memset(ins, 0, sizeof(ins));
for (register int i = 1; i <= N; ++i) {
G1[i].clear(), G2[i].clear();
}
}
}
|