链接：https://ac.nowcoder.com/acm/problem/16416
来源：牛客网
题目描述
策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对 P 取模。
如果有无穷多条合法的路线，请输出 −1。
策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对 P 取模。
如果有无穷多条合法的路线，请输出 −1。
输入描述:
第一行包含一个整数 TT, 代表数据组数。
接下来TT组数据，对于每组数据： 第一行包含四个整数 N,M,K,PN,M,K,P，每两个整数之间用一个空格隔开。
接下来MM行，每行三个整数a_i,b_i,c_iai,bi,ci，代表编号为a_i,b_iai,bi的点之间有一条权值为 c_ici的有向边，每两个整数之间用一个空格隔开。
输出描述:
输出文件包含 T 行，每行一个整数代表答案。
示例1
说明
对于第一组数据，最短路为 3。
1 - 5, 1 - 2 - 4 - 5, 1 - 2 - 3 - 5 为 3 条合法路径。
解题思路： 看到k的范围不大，可以联想到用动态规划来解决这道题。首先设dis1【i】为从1到达i点的最短距离，disn【n】为从i到达n点的最短路，状态dp【v】【j】为：从1到达V点的距离为dis1【v】+j的方案数。那么状态转移方程
为dp【v】【j】+=dp【u】【dis1【u】+j+val-dis1【v】】；进行动态规划的点的顺序，应该是dis1【i】越小的越先进行DP。还有值得注意的是当u->v的距离是零时，我们应该先对u进行状态转移，所以我们应该先对这些点进行拓扑排序，
然后对所有点进行排序来确实动态规划的顺序。
当图中存在零环的时候，并且dis1【i】+disn【i】<=dis1【n】+k时，就存在无穷多的方案数了，此时我们输出"-1"。
#include<bits/stdc++.h>
#define pi pair<int,int>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
int head[maxn];//正图
int head1[maxn];//反图
int head2[maxn];//边权为0的图
struct st{
int to,next,val;
}stm[maxn*2],stm1[maxn*2],stm2[maxn*2];
int cnt,cnt1,cnt2;
inline void read(int &x){
char ch=x=0;
int f=1;
while(!isdigit(ch)){
ch=getchar();
if(ch=='-'){
f=-1;
}
}
while(isdigit(ch))
x=x*10+ch-'0',ch=getchar();
x=x*f;
}
void add(int u,int v,int w){
stm[cnt].to=v;
stm[cnt].next=head[u];
stm[cnt].val=w;
head[u]=cnt++;
}
void add1(int u,int v,int w){
stm1[cnt1].to=v;
stm1[cnt1].next=head1[u];
stm1[cnt1].val=w;
head1[u]=cnt1++;
}
void add2(int u,int v,int w){
stm2[cnt2].to=v;
stm2[cnt2].next=head2[u];
stm2[cnt2].val=v;
head2[u]=cnt2++;
}
int dis1[maxn],disn[maxn];
int dp[maxn][55];
int n,m,k,p;
int in[maxn];
int vis[maxn];
priority_queue<pi,vector<pi>,greater<pi> > que;
int qu[maxn];
int id[maxn];
int num[maxn];
bool cmp(int u,int v){
return dis1[u]==dis1[v]?id[u]<id[v]:dis1[u]<dis1[v];
}
void dij1(){
while(!que.empty())que.pop();
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
dis1[i]=inf;
}
dis1[1]=0;
que.push(pi{0,1});
while(!que.empty()){
int now=que.top().second;
que.pop();
if(vis[now])continue;
vis[now]=1;
for(int i=head[now];~i;i=stm[i].next){
int val=stm[i].val;
int to=stm[i].to;
if(dis1[to]>dis1[now]+val){
dis1[to]=dis1[now]+val;
que.push(pi{dis1[to],to});
}
}
}
// puts("dij1");
}
void dijn(){
while(!que.empty())que.pop();
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
disn[i]=inf;
}
disn[n]=0;
que.push(pi{0,n});
// vis[n]=1;
// puts("dijn");
while(!que.empty()){
int now=que.top().second;
que.pop();
if(vis[now])continue
vis[now]=1;
for(int i=head1[now];~i;i=stm1[i].next){
int val=stm1[i].val;
int to=stm1[i].to;
// cout<<now<<" "<<to<<" "<<val<<endl;
if(disn[to]>disn[now]+val){
disn[to]=disn[now]+val;
que.push(pi{disn[to],to});
}
}
}
}
int topo(){
int h=1;
int t=0;
for(int i=1;i<=n;i++){
if(in[i]==0){
qu[++t]=i;
}
}
while(h<=t){
int now=qu[h++];
for(int i=head2[now];~i;i=stm2[i].next){
int to=stm2[i].to;
in[to]--;
if(in[to]==0)qu[++t]=to;
}
}
for(int i=1;i<=n;i++)id[qu[i]]=i;
for(int i=1;i<=n;i++){
if(in[i]&&dis1[i]+disn[i]<=dis1[n]+k)return 1;
}
return 0;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=1;i<=n;i++)num[i]=i;
int u,v,w;
memset(head,-1,sizeof(head));
cnt=0;
memset(head1,-1,sizeof(head1));
cnt1=0;
memset(head2,-1,sizeof(head2));
cnt2=0;
memset(dp,0,sizeof(dp));
memset(in,0,sizeof(in));
for(int i=0;i<m;i++){
//scanf("%d%d%d",&u,&v,&w);
read(u);
read(v);
read(w);
add(u,v,w);
add1(v,u,w);
if(w==0)add2(u,v,w),in[v]++;
}
dij1();
dijn();
/*for(int i=1;i<=n;i++){
cout<<dis1[i]<<" "<<disn[i]<<endl;
}*/
int flag=topo();
if(flag==1){
puts("-1");
continue;
}
else{
sort(num+1,num+n+1,cmp);
dp[1][0]=1;
for(int i=0;i<=k;i++){
for(int j=1;j<=n;j++){
for(int x=head[num[j]];~x;x=stm[x].next){
int to=stm[x].to;
int val=stm[x].val;
if(dis1[num[j]]+val+i-dis1[to]<=k){
dp[to][dis1[num[j]]+val+i-dis1[to]]+=dp[num[j]][i];
dp[to][dis1[num[j]]+val+i-dis1[to]]=dp[to][dis1[num[j]]+val+i-dis1[to]]%p;
}
}
}
}
int ans=0;
for(int i=0;i<=k;i++){
ans=(ans+dp[n][i])%p;
}
printf("%d
",ans);
}
}
return 0;
}
除了DP，这道题还可以用记忆化搜索来解。设dp【i】【j】为从i到n距离小于等于disn【i】+j。那么dis【u】【j】+=dis【v】【j-(disn【v】-disn【u】+val)】。当某个状态还没有计算出来再次搜到这个状态是即输出“-1”
#include<bits/stdc++.h> #define pai pair<int,int> #define inf 0x3f3f3f3f using namespace std; inline void read(int &x){ char ch=x=0; int f=1; while(!isdigit(ch)){ ch=getchar(); if(ch=='-'){ f=-1; } } while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); x=x*f; } const int maxn=1e5+5; struct st{ int to,next,val; }stm[maxn*2],stm1[maxn*2]; int head[maxn],head1[maxn]; int cnt,cnt1; int n,m,k,p; void add(int u,int v,int w){ stm[cnt].to=v; stm[cnt].val=w; stm[cnt].next=head[u]; head[u]=cnt++; } void add1(int u,int v,int w){ stm1[cnt1].to=v; stm1[cnt1].val=w; stm1[cnt1].next=head1[u]; head1[u]=cnt1++; } int dp[maxn][55]; int dis[maxn]; int vis[maxn]; priority_queue<pai,vector<pai>,greater<pai> >que; void dij(){ for(int i=1;i<=n;i++){ dis[i]=inf; vis[i]=0; } dis[n]=0; while(!que.empty())que.pop(); que.push(pai{dis[n],n}); while(!que.empty()){ int now=que.top().second; que.pop(); if(vis[now])continue; vis[now]=1; // cout<<now<<endl; for(int i=head1[now];~i;i=stm1[i].next){ int to=stm1[i].to; int val=stm1[i].val; if(dis[to]>dis[now]+val){ dis[to]=dis[now]+val; que.push(pai{dis[to],to}); } } } } int sta[maxn][55]; int dfs(int u,int j){ // cout<<u<<endl; if(sta[u][j])return -1; if(dp[u][j]!=0)return dp[u][j]; sta[u][j]=1; dp[u][j]=(u==n?1:0); for(int i=head[u];~i;i=stm[i].next){ int to=stm[i].to; int val=stm[i].val; if(dis[to]-dis[u]+val<=j){ int tem=dfs(to,j-(dis[to]-dis[u]+val)); if(tem==-1)return dp[u][j]=-1; dp[u][j]=(dp[u][j]+tem)%p; } } sta[u][j]=0; return dp[u][j]; } int main(){ int t; read(t); while(t--){ read(n); read(m); read(k); read(p); int u,v,w; memset(head,-1,sizeof(head)); cnt=0; memset(head1,-1,sizeof(head1)); memset(sta,0,sizeof(sta)); memset(dp,0,sizeof(dp)); cnt1=0; for(int i=0;i<m;i++){ read(u); read(v); read(w); add(u,v,w); add1(v,u,w); } dij(); // dp[n][0]=1; int ans=dfs(1,k); printf("%d ",ans); } return 0; }