参考了 这篇题解
这个方法常数还是比较大的,需要注意
加了快读都很勉强,还需要加上register int(是说luogu,acwing直接过了…)
大体思路就是记忆化搜索
先跑一遍spfa(dijkstra)预处理
然后从起点出发
状态为f[i][j]表示从起点到i号点剩余可多走路程为j
j < 0自然直接返回0
到达终点时当前方案数++,一直跑就完事了
注意判0环
无穷多组解的情况当且仅当在一个可行(比最短路长不超过k)路径上存在零环
luogu有hack数据,建议去交一发
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define rint register int
using namespace std;
const int N = 1e5 + 5,M = 4e5 + 5,inf = 0x3f3f3f3f;
int h[N],rh[N],e[M],ne[M],w[M],idx;
int n,m,k,mod,dis[N],f[N][55];
bool alive[N],st[N],vis[N][55],over[N][55];
queue<int> q1;
void init()
{
memset(h,0,sizeof h);
memset(rh,0,sizeof h);
memset(vis,0,sizeof vis);
idx = 0;
memset(f,-1,sizeof f);
memset(alive,0,sizeof alive);
}
void add(int h[],int u,int v,int wi)
{
ne[++ idx] = h[u];
e[idx] = v;
w[idx] = wi;
h[u] = idx;
}
void dfs_alive(int u)
{
alive[u] = 1;
for(rint i = rh[u]; i ;i = ne[i])
{
int v = e[i];
if(alive[v])continue;
dfs_alive(v);
}
}
void spfa()
{
memset(dis,inf,sizeof dis);
q1.push(1);
dis[1] = 0;
st[1] = 1;
while(q1.size())
{
int u = q1.front();q1.pop();
st[u] = 0;
for(rint i = h[u]; i ;i = ne[i])
{
int v = e[i];
if(dis[v] > dis[u] + w[i])
{
dis[v] = dis[u] + w[i];
if(!st[v])q1.push(v);
st[v] = 1;
}
}
}
}
int dfs(int u,int res)
{
if(res < 0)return 0;
if(vis[u][res]){over[u][res] = 1;return 0;}
if(f[u][res] != -1)return f[u][res];
vis[u][res] = 1;
int now = u == n;
for(rint i = h[u]; i ;i = ne[i])
{
int v = e[i];
if(!alive[v])continue;
int t = dfs(v,res - ( w[i] - (dis[v] - dis[u]) ));
if(t == -1)return -1;
now = (now + t) % mod;
}
vis[u][res] = 0;
f[u][res] = now;
if(f[u][res] > 0 && over[u][res])return -1;
return now;
}
int read()
{
int res = 0;
char c = getchar();
while(c < '0' || c > '9')c = getchar();
while(c >= '0' && c <= '9')
{
res = res * 10 + c - '0';
c = getchar();
}
return res;
}
int main()
{
int T;
T = read();
while(T --)
{
init();
n = read(),m = read(),k = read(),mod = read();
for(rint i = 1;i <= m;i ++)
{
int xi,yi,ci;
xi = read(),yi = read(),ci = read();
add(h,xi,yi,ci);
add(rh,yi,xi,ci);
}
dfs_alive(n);
spfa();
cout << dfs(1,k) << endl;
}
}