题目描述
策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对 P取模。
如果有无穷多条合法的路线，请输出 −1。
输入格式
第一行包含一个整数 T, 代表数据组数。
接下来 T 组数据，对于每组数据：
第一行包含四个整数 N,M,K,P 每两个整数之间用一个空格隔开。
接下来 M 行，每行三个整数 ai,bi,ci， 代表编号为 ai,bi 的点之间有一条权值为 ci 的有向边，每两个整数之间用一个空格隔开。
输出格式
输出文件包含 T 行，每行一个整数代表答案。
此题仔细研究一下就可以发现是一道DP虽然我考试时没看出来，先求出1到任一点的最短路（dijkstra，SPFA，Floyd）之后开始d（对）p（拍），子状态dp[u][k]代表从1号节点到u号节点路径长度为dis[u](1到u的最短路) + k的路径条数，
转移方程：∑dp[v][dis[u] - dis[v] + k - edge(u, v)]（dfs跑反图，求dp[n][0~k]），再判一下有没有"0"环即可。
上代码：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX = 1e5 + ;
struct node{
int pre, to, val;
}edge[ * MAX];
int head[MAX], tot;
int dis[MAX], dp[MAX][];
bool vis[MAX], vis2[MAX][];
int a[ * MAX], b[ * MAX], c[ * MAX];
int T, n, m, k, p, ans;
bool zero;
void insert(int u, int v, int len) {
edge[++tot] = node{head[u], v, len};
head[u] = tot;
}
int read() {
int ret = ;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) ret = ret * + ch - '', ch = getchar();
return ret;
}
priority_queue<pair<int, int> > q;
void dijkstra() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, , sizeof(vis));
dis[] = ;
q.push(make_pair(, ));
while (!q.empty()) {
int x = q.top().second;
q.pop();
if (vis[x]) continue;
vis[x] = ;
for (int i = head[x]; i; i = edge[i].pre) {
int y = edge[i].to, z = edge[i].val;
if (dis[y] > dis[x] + z) {
dis[y] = dis[x] + z;
q.push(make_pair(-dis[y], y));
}
}
}
}
int dfs(int x, int now_k) {
if (dp[x][now_k] != -) return dp[x][now_k];
vis2[x][now_k] = ;
dp[x][now_k] = ;
for (int i = head[x]; i; i = edge[i].pre) {
int y = edge[i].to, z = edge[i].val;
int next_k = dis[x] - dis[y] + now_k - z;
if (next_k < ) continue;
if (vis2[y][next_k]) zero = ;
dp[x][now_k] += dfs(y, next_k);
//cout << dp[x][now_k] << endl;
if (dp[x][now_k] > p) dp[x][now_k] -= p;
}
vis2[x][now_k] = ;
return dp[x][now_k];
}
int main() {
T = read();
while (T--) {
memset(head, , sizeof(head));
memset(dp, -, sizeof(dp));
memset(vis2, , sizeof(vis2));
tot = ;
ans = ;
zero = ;
n = read(), m = read(), k = read(), p = read();
for (int i = ; i <= m; i++) {
a[i] = read(), b[i] = read(), c[i] = read();
insert(a[i], b[i], c[i]);
}
dijkstra();
memset(head, , sizeof(head));
tot = ;
for (int i = ; i <= m; i++) {
insert(b[i], a[i], c[i]);
}
dp[][] = ;
for (int i = ; i <= k; i++) {
ans += dfs(n, i);
//puts("");
if (ans > p) ans -= p;
}
dfs(n, k + );
if (zero) {
puts("-1");
continue;
}
cout << ans << "\n";
}
return ;
}