题目链接：https://www.luogu.org/problemnew/show/P3953
30分很好拿的样子，就是(k=0)的情况我们可以直接跑最短路计数；（代码之后放）
但是这个题应该算是一个DP题（至少我认为记忆化搜索属于DP的范畴），时间复杂度(O(TNK))。
状态设计为(sum[i][j])表示到节点(i)比它最短路长(j)的路径个数。
那么显然状态转移方程为：$$sum[v][j]=sum sum[u][dis[v]+j-w-dis[u]]$$其中(u)是指向(v)的边，(w)是节点(u,v)之间的边长。
这里需要注意的一点是由于状态转移方程的缘故，我们需要使用搜索回溯来更新状态取值。所以我们要从终点往前搜索。那么很显然的，我们需要建立反图。
之后就是怎么判断负环了。
我开始有一种T两个点的垃圾做法是在spfa上面直接判断，状态更新的判断为
if(dis[v]>=dis[u]+edge[i].dis)
但是这种做法显然很菜，之后想了想可以直接在搜索中判断，如果一个被赋予值的状态在栈中重复被访问，显然是有0环了，就直接输出-1即可。
但是可能我的写法有点神仙，所以过不了样例那种情况（就是两个点的0环情况），所以虽然代码过了题，大家写的时候还是加上特判比较好qwq。
还有就是注意多组数据的初始化。。。别学我的辣鸡初始化，最好还是写个(init())函数。。
以下是AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define MAXN 100010
#define MAXM 200010
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,m,k,p,t,edge_number,tot,ff;
int dis[MAXN],siz[MAXN],sum[MAXN][55],head[MAXN],head2[MAXN],done[MAXN],vis[MAXN][55];
struct Edge{int nxt,to,dis;}edge[MAXM<<1],edge2[MAXM<<1];
inline void add(int from,int to,int dis)
{
edge[++edge_number].dis=dis;
edge[edge_number].to=to;
edge[edge_number].nxt=head[from];
head[from]=edge_number;
}
inline void add2(int from,int to,int dis)
{
edge2[++tot].dis=dis;
edge2[tot].to=to;
edge2[tot].nxt=head2[from];
head2[from]=tot;
}
inline bool spfa()
{
queue<int>q;
memset(dis,0x3f,sizeof(dis));
memset(done,0,sizeof(done));
q.push(1); done[1]=1; dis[1]=0;
while(!q.empty())
{
int u=q.front(); q.pop(); done[u]=0;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;
siz[v]=siz[u]+1;
if(siz[v]>=n)
return false;
if(!done[v])
{
q.push(v);
done[v]=1;
}
}
}
}
return true;
}
inline int search(int u,int w)
{
if(sum[u][w]>=0) return sum[u][w];
vis[u][w]=1;
sum[u][w]=0;
for(register int i=head2[u];i;i=edge2[i].nxt)
{
int v=edge2[i].to;
int cur=dis[u]+w-dis[v]-edge2[i].dis;
if(cur<0) continue;
if(vis[v][cur]) return -1;
sum[u][w]+=search(v,cur),sum[u][w]%=p;
}
vis[u][w]=0;
return sum[u][w];
}
inline int solve()
{
int ans=0;
sum[1][0]=1;
for(register int i=0;i<=k;i++)
{
int cur=search(n,i);
if(cur==-1) return -1;
ans+=search(n,i);
ans%=p;
}
return ans;
}
int main()
{
t=read();
while(t--)
{
memset(sum,-1,sizeof(sum));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
memset(head2,0,sizeof(head2));
edge_number=0;
tot=0,ff=0;
n=read(),m=read(),k=read(),p=read();
for(register int i=1;i<=m;i++)
{
int u,v,w;
u=read(),v=read(),w=read();
add(u,v,w);
add2(v,u,w);
}
spfa();
printf("%d
",solve());
}
return 0;
}
以下。。。。。。是30分代码：
qwqwq
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 100010
using namespace std;
int t,n,m,k,p,edge_number,ans,minn;
int head[MAXN],dis[MAXN],done[MAXN],siz[MAXN];
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
void add(int from,int to,int dis)
{
edge[++edge_number].dis=dis;
edge[edge_number].to=to;
edge[edge_number].nxt=head[from];
head[from]=edge_number;
}
inline bool spfa()
{
queue<int>q;
memset(dis,0x3f,sizeof(dis));
memset(done,0,sizeof(done));
q.push(1); done[1]=1; dis[1]=0;
while(!q.empty())
{
int u=q.front(); q.pop(); done[u]=0;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(dis[v]>=dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;
siz[v]=siz[u]+1;
if(siz[v]>=n)
return false;
if(!done[v])
{
q.push(v);
done[v]=1;
}
}
}
}
return true;
}
inline void search(int now,int dis)
{
if(dis>minn+k) return;
if(now==n)
ans=(ans+1)%p;
for(int i=head[now];i;i=edge[i].nxt)
search(edge[i].to,dis+edge[i].dis);
}
int main()
{
scanf("%d",&t);
while(t--)
{
edge_number=0,ans=0;
memset(head,0,sizeof(head));
memset(done,0,sizeof(done));
memset(siz,0,sizeof(siz));
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
if(spfa()==false){
printf("-1
");
continue;
}
minn=dis[n];
//for(int i=1;i<=n;i++) printf("dis[%d]=%d
",i,dis[i]);
search(1,0);
printf("%d
",ans);
}
return 0;
}