这道题是一道不错的计数类DP；
首先我们一定要跑一遍dijkstra来求得每个点到1号点的最短路；
注意题干，题中并没有说所有点都可以到达n好点，只说了存在一条1号点到n号点的路径；所以我们在反向图上BFS求出那些点可以到达n号点;
然后就是dp。我们设计状态:f[u][rest]表示到达u号点时，还可以走额外rest这么长的路；很显然得：f[u][rest]=sigma(f[v][rest-w+dis[v]-dis[u]])
其中dis[u]表示从1到u得最短路；w表示从u到v的边权；
为了在图中DP方便，可以采用记忆化搜索来进行记数;
判断是否输出-1的方法：如果这个状态在栈里，那么输出-1；表示存在0环；
特别注意：当判断-1时，你可能返回-INT_MAX来表示结束程序，但这道题的模数比较小，所以一定不能在返回-INT_MAX时把这个数取模，否则会输出一个负数（不是-INT_MAX），让程序继续进行，并不能输出-1；
#include <bits/stdc++.h>
const int INF=0x7FFFFFFF;
using namespace std;
struct littlestar{
int to;
int nxt;
int w;
}star[400010],star2[400010];
int head[400010],cnt,head2[400010],cnt2;
void add(int u,int v,int w)
{
star[++cnt].to=v;
star[cnt].nxt=head[u];
head[u]=cnt;
star[cnt].w=w;
}
void add2(int u,int v,int w)
{
star2[++cnt2].to=v;
star2[cnt2].nxt=head2[u];
star2[cnt2].w=w;
head2[u]=cnt2;
}
int n,m,k,p;
int dis[100010],vis[100010],bo[100010];
int ans[100010][51];
int st[100010][51];
inline void pre()
{
memset(bo,0,sizeof(bo));
memset(ans,-1,sizeof(ans));
memset(st,0,sizeof(st));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
memset(head2,0,sizeof(head2));
cnt=0;
cnt2=0;
}
priority_queue<pair<int,int> > q;
void dijkstra()
{
q.push(make_pair(0,1));
dis[1]=0;
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(register int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
}
queue<int> q2;
void panduan()
{
q2.push(n);
bo[n]=1;
while(q2.size()){
int u=q2.front();
q2.pop();
for(register int i=head2[u];i;i=star2[i].nxt){
int v=star2[i].to;
if(bo[v]==0){
q2.push(v);
bo[v]=1;
}
}
}
}
int dp(int u,int rest)
{
if(rest<0) return 0;
if(st[u][rest]==1) return -INF;
if(ans[u][rest]!=-1) return ans[u][rest];
long long tmpans=0;
st[u][rest]=1;
if(u==n) ++tmpans;
for(register int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(bo[v]==0) continue;
int ha=dis[v]-dis[u];
int tmp=dp(v,rest-(star[i].w-ha));
if(tmp==-INF){
return -INF;
}
else{
tmpans=(tmpans+tmp)%p;
}
}
ans[u][rest]=tmpans%p;
st[u][rest]=0;
return tmpans;
}
int main()
{
int t;
cin>>t;
while(t--){
pre();
cin>>n>>m>>k>>p;
for(register int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add2(v,u,w);
}
for(int i=1;i<=n;i++) dis[i]=INF;
dijkstra();
panduan();
long long w=dp(1,k);
if(w==-INF){
cout<<"-1"<<endl;
}
else{
cout<<w<<endl;
}
}
}
原文：https://www.cnblogs.com/kamimxr/p/11624066.html