[洛谷P3953]逛公园
/ / 阅读耗时 9 分钟难度：省选/NOI-
题目描述
策策同学特别喜欢逛公园。公园可以看成一张$N$个点$M$条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，$N$号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从1号点进去，从$N$号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点到$N$号点的最短路长为$d$，那么策策只会喜欢长度不超过$d + K$的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？
为避免输出过大，答案对$P$取模。
如果有无穷多条合法的路线，请输出-1。
对于$100\%$的数据, $1 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 1000,k\leq 50$。
输入输出格式
输入格式：
第一行包含一个整数$T$, 代表数据组数。
接下来$T$组数据，对于每组数据：第一行包含四个整数$N,M,K,P$每两个整数之间用一个空格隔开。
接下来MM行，每行三个整数$a_i,b_i,c_i$，代表编号为$a_i,b_i$的点之间有一条权值为$c_i$的有向边，每两个整数之间用一个空格隔开。
输出格式：
输出文件包含$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
题解
最短路计数类题目，还算比较常规。
首先一遍Dijkstra算法求最短路。这里如果要求最短路的走法个数可以规定$dp(i)$为从$i$开始的最短路数目，然后向出点转移即可。但是由于$k$的存在，需要给$dp$加一维成为$dp(i,j)$，表示从$i$开始走，并且最大允许多走$j$个单位的路径可以得到的方案数，这个方法可行主要是利用了$k$较小的特点。
其实这可以认为是DP类的题目，但是与DP问题稍有不同，严格来说应该叫记忆化搜索。当求$dp(i,j)$时，会递归地去求很多相关的$dp$数据，如果此时又回到$dp(i,j)$，说明存在0环，方案数就是无穷大。在这个问题的处理中，我们需要用搜索式的方法来确定$dp(i,j)$的最终值，因此与常规的DP不同，称为记忆化搜索更为贴切。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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
using namespace std;
inline int read() {
char e = getchar();
int s = 0;
while (e < '-')e = getchar();
while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
return s;
}
struct Edge {
int next, v, to;
} edge[200005], edge2[200005];
int n, m, k, p, cnt, head[100005], dis[100005], dp[100005][55], cnt2, head2[100005], na[100005];
int heap[100005], ID[100005], size;
bool vis[100005][55], lk;
inline void add(int x, int y, int z) {
edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
edge2[cnt2].to = x, edge2[cnt2].next = head2[y], edge2[cnt2].v = z, head2[y] = cnt2++;
}
int DP(int x, int y) {//DP过程
if (lk)return 0;
if (vis[x][y]) {
vis[x][y] = false, lk = true;
return 0;
}
if (dp[x][y] != -1)return dp[x][y];
vis[x][y] = true, dp[x][y] = x == n;
for (int i = head[x]; i; i = edge[i].next) {
if (dis[x] + edge[i].v - dis[edge[i].to] <= y && na[edge[i].to]) {
dp[x][y] += DP(edge[i].to, y - (dis[x] + edge[i].v - dis[edge[i].to])), dp[x][y] %= p;
}
}
vis[x][y] = false;
return dp[x][y];
}
void DFS(int x) {
na[x] = 1;
for (int i = head2[x]; i; i = edge2[i].next)if (!na[edge2[i].to])DFS(edge2[i].to);
}
inline void solve(int x) {
int x1 = x << 1, x2 = x << 1 | 1, minn = x;
if (x1 <= size && dis[heap[x1]] < dis[heap[minn]])minn = x1;
if (x2 <= size && dis[heap[x2]] < dis[heap[minn]])minn = x2;
if (minn != x)swap(ID[heap[minn]], ID[heap[x]]), swap(heap[minn], heap[x]), solve(minn);
}
inline int top() {
int r = heap[1];
heap[1] = heap[size--], ID[heap[1]] = 1, solve(1);
return r;
}
inline void up(int x) {
if (x == 1)return;
if (dis[heap[x >> 1]] > dis[heap[x]])
ID[heap[x >> 1]] = x, ID[heap[x]] = x >> 1, swap(heap[x >> 1], heap[x]), up(x >> 1);
}
inline void add(int x) {
heap[++size] = x, ID[x] = size, up(size);
}
int main() {
// freopen("text.in", "r", stdin);
int t = read(), ans = 0;
while (t--) {
n = read(), m = read(), k = read(), p = read(), lk = false, cnt = 1, cnt2 = 1;
for (register int i = 1; i <= n; i++) {
dis[i] = inf, head2[i] = head[i] = 0, na[i] = 0, ID[i] = 0;
for (register int j = 0; j <= k; j++)dp[i][j] = -1;
}
for (int i = 1, x, y, z; i <= m; i++)x = read(), y = read(), z = read(), add(x, y, z);
dis[1] = 0, add(1);
while (size > 0) {
int i1 = top();
for (register int i = head[i1]; i; i = edge[i].next) {
if (dis[i1] + edge[i].v < dis[edge[i].to]) {
dis[edge[i].to] = dis[i1] + edge[i].v;
if (ID[edge[i].to] != 0)up(ID[edge[i].to]);
else add(edge[i].to);
}
}
}
DFS(n), ans = DP(1, k);
if (lk)cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}