求有向图中 \(1\) 到 \(n\) 的路径中长度小于等于 \(dis(1,n)+k\) 的方案数。\(dis(1,n)\) 表示最短路。\(k\le 50\)。
部分分 \(k=0\)，直接最短路计数即可。
我们发现有向图中存在后效性，不好动态规划，但我们仔细思考后，在不存在 \(0\) 边的情况下，设 \(f(u,k)\) 表示从 \(1\) 走到 \(u\) 时长度为 \(k\) 的方案数，若存在 \(f(v,j)\) 需要转移到它身上，那么有 \(k\ne j\)，不存在后效性。所以最简单的：
\[f(u,k)\rightarrow f(v,k+w(u,v)) \]而这并不好实现，因为我们无法确定 dp 顺序，也就是不能保证有拓扑序。而我们发现 \(k\) 很小，我们只关心 \(dis(1,n)+k\) 以内的路径，并且对于 \(1\) 到 \(u\) 的路径，长度一定大于等于 \(dis(1,u)\)。所以状态写成 \(f(u,k)\) 表示从 \(1\) 走到 \(n\) 时长度为 \(dis(1,u)+k\) 的方案数。
假设 \(f(u,k)\) 可以转移到 \(f(v,x)\)，那么有
\(dis(1,u)+k+w(u,v)=dis(1,v)+x\)
\(x=dis(1,u)+k+w(u,v)-dis(1,v)\)
所以 \(f(u,k)\rightarrow f(v,dis(1,u)+k+w(u,v)-dis(1,v))\)
70pts：此时我们转移就可以把按 \(dis\) 值从小到大排序转移（对于无 \(0\) 边）。
100pts：一样有无后效性，因为对于 \(k=x\) 时，\(dis(1,u)+w(u,v)=dis(1,v)\) 为最短路上的拓扑序，所有最短路构成的图是 \(DAG\)；而其他情况则是分层图上不同层的转移，同样有无后效性。
但有一个特殊情况就是图中 \(1\) 到 \(n\) 的路径中存在 \(0\) 环，特判一下就可以转移了。可以用记忆化搜索，实现起来细节不多。
总结：特殊性质的优化，变为无后效性问题
#include <bits/stdc++.h>
typedef long long ll;
int read() {
int x = 0, f = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) {
x = (x << 3) + (x << 1) + (c - '0');
c = getchar();
}
return x * f;
}
bool flg;
int t, n, m, k, p, cnt, cnt2, ans;
int h[100010], h2[100010], dis[100010], vis[100010], f[100010][51], ins[100010][51];
struct node {
int to, nxt, w;
} e[200010], e2[200010];
void add(int u, int v, int w) {
e[++cnt].to = v;
e[cnt].nxt = h[u];
e[cnt].w = w;
h[u] = cnt;
}
void add2(int u, int v, int w) {
e2[++cnt2].to = v;
e2[cnt2].nxt = h2[u];
e2[cnt2].w = w;
h2[u] = cnt;
}
struct ac {
int v, w;
friend bool operator < (ac a, ac b) {
return a.w > b.w;
}
} tmp;
void dij(int s) {
std::priority_queue<ac> q;
for(int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f, vis[i] = 0;
dis[s] = 0;
q.push({s, 0});
while(!q.empty()) {
int u = q.top().v;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
tmp.v = v, tmp.w = dis[v];
q.push(tmp);
}
}
}
}
int dp(int u, int j) {
if(j < 0) return 0;
if(ins[u][j]) {
flg = 1;
return 0;
}
if(f[u][j]) return f[u][j];
ins[u][j] = 1;
int ret = 0;
for(int i = h2[u]; i; i = e2[i].nxt) {
int v = e2[i].to;
ret = (ret + dp(v, dis[u] + j - e2[i].w - dis[v])) % p;
if(flg) return 0;
}
ins[u][j] = 0;
return f[u][j] = ret;
}
void Solve() {
t = read();
while(t--) {
n = read(), m = read(), k = read(), p = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
add(u, v, w), add2(v, u, w);
}
dij(1);
ans = 0, flg = 0;
memset(f, 0, sizeof(f));
memset(ins, 0, sizeof(ins));
dp(1, 0);
f[1][0] = 1;
for(int i = 0; i <= k; i++) {
ans = (ans + dp(n, i)) % p;
}
if(flg) std::cout << "-1\n";
else std::cout << ans << "\n";
for(int i = 1; i <= n; i++) {
h[i] = h2[i] = 0;
}
cnt = cnt2 = 0;
}
}
int main() {
Solve();
return 0;
}