传送门
解题思路
令 (dp[i][j]) 表示从 (1) 号点到 (i) 号点的长度比最短路多 (j) 的路径的条数。
则答案为：
[ans=sum_{i=0}^{k}dp[n][i]
]
从 (n) 开始在反图上进行转移，转移方程为：
[dp[u][k]=sum dp[v][k-(value-(dis[u]-dis[v]))]
]
其中 (v) 为 (u) 的子节点，(value) 为边权，(dis[i]) 为 (1) 号点到 (i) 号点的最短路长度。
初始化：(dp[1][0]=1)
判断是否经过零环：若求解某个dp值时有用到了此dp值，则必有零环。
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100005;
int T,n,m,mod,k,dp[maxn][55],dis[maxn],p[maxn],P[maxn],cnt1,cnt2;
int on[maxn],in[maxn],vis[maxn][55],wrong;
struct node{
int u,v,w,next;
}e[maxn*2],E[maxn*2];
void insert1(int u,int v,int w){
cnt1++;
e[cnt1].u=u;
e[cnt1].v=v;
e[cnt1].w=w;
e[cnt1].next=p[u];
p[u]=cnt1;
}
void insert2(int u,int v,int w){
cnt2++;
E[cnt2].u=u;
E[cnt2].v=v;
E[cnt2].w=w;
E[cnt2].next=P[u];
P[u]=cnt2;
}
void dfs1(int u){
on[u]=1;
for(int i=p[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(on[v]) continue;
dfs1(v);
}
}
void spfa(){
memset(dis,0x3f,sizeof(dis));
memset(in,0,sizeof(in));
queue<int> q;
in[1]=1;
dis[1]=0;
q.push(1);
while(!q.empty()){
int u=q.front();
q.pop();
in[u]=0;
for(int i=p[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!in[v]){
q.push(v);
in[v]=1;
}
}
}
}
}
int dfs(int u,int now){
if(now<0) return 0;
if(vis[u][now]){
wrong=1;
return dp[u][now]=0;
}
if(dp[u][now]!=-1) return dp[u][now];
dp[u][now]=0;
vis[u][now]=1;
for(int i=P[u];i!=-1;i=E[i].next){
int v=E[i].v;
if(!on[v]) continue;
dp[u][now]=(dp[u][now]+dfs(v,now-(E[i].w-(dis[u]-dis[v]))))%mod;
}
vis[u][now]=0;
if(u==1&&now==0) dp[u][now]=1;
return dp[u][now];
}
void work(){
dfs1(1);
spfa();
int ans=0;
wrong=0;
for(int i=0;i<=k;i++){
ans=(ans+dfs(n,i))%mod;
if(wrong==1){
printf("-1
");
return;
}
}
printf("%d
",ans);
}
int main(){
cin>>T;
while(T--){
memset(on,0,sizeof(on));
memset(p,-1,sizeof(p));
memset(P,-1,sizeof(P));
memset(dp,-1,sizeof(dp));
cnt1=cnt2=0;
cin>>n>>m>>k>>mod;
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert1(u,v,w);
insert2(v,u,w);
}
work();
}
return 0;
}
//NOIP2017提高组Day1 t3