题目链接
https://www.luogu.org/problemnew/show/P3953
题解
设(dis[i])为(i)到(1)的最短路
令(f[i][k])为路径等于(dis[i]+k)的个数,则(f[i][k])可以由能到达(i)的并且距离为(dis[i]+j-dis(i,j))的点转移过来
则转移为
[f[i][k]=sum f[j]left[dis[i]+k-dis(i,j)-dis[j]
ight]
]
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1e5+10;
int n,m,d,k,p,ans;
int dis[maxn],vis[maxn];
int head[maxn],cnt,flag,Head[maxn];
queue<int>q;
struct edge{int to,nxt,w;}e[maxn*2],E[maxn*2];
void add(int x,int y,int z){
e[++cnt]=(edge){y,head[x],z};
E[cnt]=(edge){x,Head[y],z};
head[x]=cnt;
Head[y]=cnt;
}
void spfa(){
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(1);vis[1]=1;dis[1]=0;
while(!q.empty()){
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x];i;i=e[i].nxt){
int u=e[i].to;
if(dis[u]>dis[x]+e[i].w){
dis[u]=dis[x]+e[i].w;
if(!vis[u]){
vis[u]=1;q.push(u);
}
}
}
}
}
int f[maxn][60],tag[maxn][60];
int dfs(int x,int t){
if(tag[x][t]){
flag=0;
return 0;
}
if(f[x][t]!=-1)return f[x][t];
tag[x][t]=1;
f[x][t]=0;
for(int i=Head[x];i;i=E[i].nxt){
int u=E[i].to;
int c=dis[x]+t-E[i].w-dis[u];
if(c>=0) f[x][t]=(f[x][t]+dfs(u,c))%p;
}
tag[x][t]=0;
return f[x][t];
}
int main(){
ios::sync_with_stdio(false);
int T;cin>>T;
while(T--){
memset(f,-1,sizeof(f));
memset(head,0,sizeof(head));
memset(tag,0,sizeof(tag));
memset(Head,0,sizeof(Head));
ans=0;cnt=0;
cin>>n>>m>>k>>p;
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
add(x,y,z);
}
spfa();
f[1][0]=flag=1;
for(int i=0;i<=k;i++) ans=(ans+dfs(n,i))%p;
dfs(n,k+1);
if(flag)cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}