problem
一个有向无重边自环图，设$D$为从$1$号点走到$n$号点的最短距离。问有多少条从$1$到$n$的路径长度不超过$D+K$。$K$为给定的值，且$K\le 50$
如果有无数条，输出-1
solution
下面有$dis[i]$表示$i$号点到$n$号点的最短路径长度。
设$f[i][j]$表示从$i$号点走到$n$号点，走了$j$的多余路径的方案数。就有如下转移:
\[f[i][j]=\sum\limits_{i,v之间有边}f[v][j-(dis[v]+w-dis[i])]\]记忆化搜索即可。
注意到如果出现了无数条路径，肯定出现了0环。也就是某一个状态被访问了两次。记忆化搜索的过程中标记一下即可。
code
#include<cstdio>
#include<iostream>
#include<ctime>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
struct node {
int v,nxt,w;
}e[N << 1],E[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
int head2[N],ejs2;
void add2(int u,int v,int w) {
E[++ejs2].v = v;E[ejs2].w = w;E[ejs2].nxt = head2[u];head2[u] = ejs2;
}
queue<int>q;
int n,m,K,mod,dis[N],vis[N];
void spfa(int U) {
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[U] = 0;
q.push(U);
while(!q.empty()) {
int u = q.front();q.pop();vis[u] = 0;
for(int i = head2[u];i;i = E[i].nxt) {
int v = E[i].v;
if(dis[v] > dis[u] + E[i].w) {
dis[v] = dis[u] + E[i].w;
if(!vis[v]) {
vis[v] = 1;q.push(v);
}
}
}
}
}
int bz[N][60],f[N][60];
int dfs(int u,int x) {
if(bz[u][x] == 2) return f[u][x];
if(bz[u][x] == 1) return -1;
bz[u][x] = 1;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
int w = x - (dis[v] + e[i].w - dis[u]);
if(w < 0 || w > K) continue;
int k = dfs(v,w);
if(k == -1) return -1;
f[u][x] += k;
f[u][x] %= mod;
}
bz[u][x] = 2;
return f[u][x];
}
int main() {
int T = read();
while(T--) {
memset(head,0,sizeof(head));
ejs2 = 0;
memset(head2,0,sizeof(head2));
ejs = 0;
n = read(),m = read(),K = read(),mod = read();
memset(f,0,sizeof(f));
memset(bz,0,sizeof(bz));
for(int i = 1;i <= m;++i) {
int u = read(),v = read(),w = read();
add(u,v,w);
add2(v,u,w);
}
spfa(n);
f[n][0] = 1;
int ans = 0;
for(int i = 0;i <= K;++i) {
int k = dfs(1,i);
if(k == -1) {
ans = -1;break;
}
ans += k;
ans %= mod;
}
printf("%d\n",ans);
}
return 0;
}