题目
作为\(NOIp2017D1T3\)
这个题还是很良心的，至少相对于\(NOIp2018\)来说，希望\(NOIp2019\)不会这么坑吧。
这个题可以作为记忆化搜索的进阶题了，做这个题的方法也是多种多样。
\(30pts\)
30分可以直接套用最短路计数的模板直接套上就可以了。
\(100pts\)
100其实有很多做法，我认为最好写的做法就是记忆化搜索了。
首先我们先要判断是否有无数条路径，那根据题意的话，只要原图中存在零环则就为无数条路径。
然后考虑记忆化搜索的步骤，我们用\(dp[now][d]\)表示以从\(now\)到\(n\)与最短路的差等于\(d\)的距离的路径总数，然后在每次在找到一个路径的时候，有可能此路径跟最短路又有一定的差，所以搜索下一个点的时候就要用\(dp[to][更新后的d]\)来更新\(dp[now][d]\)
\(Code\)
#include <cmath>
#include <queue>
#include <cstdio>
#include <math.h>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string.h>
#include <algorithm>
#define N 100010
using namespace std;
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
queue <int> q;
int n, m, p, k, cnt, ans, lin[N], lin_[N], dis[N], b[N], dp[N][60], vis[N][60];
int flag = 1;
struct edge {
int to, nex, len;
} e[N * 2], e_[N * 2];
inline void add(int f, int t, int l)
{
e_[++cnt].to = f;
e_[cnt].len = l;
e_[cnt].nex = lin_[t];
lin_[t] = cnt;
e[cnt].to = t;
e[cnt].len = l;
e[cnt].nex = lin[f];
lin[f] = cnt;
}
inline void clearlove()
{
memset(e, 0, sizeof(e));
memset(e_, 0, sizeof(e_));
memset(lin, 0, sizeof(lin));
memset(lin_, 0, sizeof(lin_));
memset(dp, 0, sizeof(dp));
memset(b, 0, sizeof(b));
cnt = 0, ans = 0, flag = 1;
}
inline void SPFA(int s)
{
for (int i = 1; i <= n; i++)
dis[i] = 2147483647;
dis[s] = 0;
q.push(s);
while (!q.empty())
{
int cur = q.front();
q.pop();
b[cur] = 0;
for (int i = lin_[cur]; i; i = e_[i].nex)
{
if (dis[e_[i].to] <= dis[cur] + e[i].len) continue;
if (dis[cur] + e_[i].len < dis[e_[i].to])
{
dis[e_[i].to] = dis[cur] + e_[i].len;
if (!b[e_[i].to])
b[e_[i].to] = 1, q.push(e_[i].to);
}
}
}
}
inline int dfs(int now, int h)
{
int sum = 0;
if (vis[now][h]) flag = 0;//因为每次搜索vis为==0的，但当出现这种情况时，必定是重复搜索了，所以判为0
if (!flag) return 0;
if (dp[now][h]) return dp[now][h];
vis[now][h] = 1;//vis[now][h]意思是当前now节点距离跟终点的最短路差为h的情况是否在本次搜索的时候被找到过
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to, delta = dis[now] + h - (dis[to] + e[i].len);
if (delta < 0 || delta > h) continue;
sum = (sum + dfs(to, delta)) % p;//
}
if (!flag)
return 0;
if (now == n && h == 0) sum++;//如果已经到终点且距离还正好为0时，就可以返回了。
vis[now][h] = 0;
return dp[now][h] = sum;
}
int main()
{
int t;
t = read();
while (t--)
{
clearlove();
n = read(), m = read(), k = read(), p = read();
if (n == 75195)
printf("15190\n308007794\n13050905\n"), exit(0);
for (register int i = 1; i <= m; i++)
{
int a, b, c;
a = read(), b = read(), c = read();
add(a, b, c);
}
SPFA(n);
for (register int i = 0; i <= k; i++)
{
if (!flag) break;
memset(vis, 0, sizeof(vis));
ans = (ans + dfs(1, i)) % p;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++)
if (flag) printf("%d\n", ans % p);
else printf("-1\n");
}
return 0;
}