题目描述
策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。
策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路长为 d，那么策策只会喜欢长度不超过 d + K 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对 P 取模。
如果有无穷多条合法的路线，请输出 −1。
输入描述:
第一行包含一个整数 T, 代表数据组数。
接下来 T 组数据，对于每组数据：
第一行包含四个整数 N,M,K,P， 每两个整数之间用一个空格隔开。
接下来 M 行，每行三个整数 ai,bi,ci， 代表编号为 ai,bi 的点之间有一条权值为 ci 的有向边，每两个整数之间用一个空格隔开。
输出描述:
输出文件包含 T 行，每行一个整数代表答案。
示例1
2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0
3
-1
对于第一组数据，最短路为 3。
1 - 5, 1 - 2 - 4 - 5, 1 - 2 - 3 - 5 为 3 条合法路径。
备注
对于不同测试点，我们约定各种参数的规模不会超过如下
解答
做法
本蒟蒻选择的做法是SPFA加dp，看很多大佬都要加拓扑什么的来确定dp更新顺序和判0环，不过本蒟蒻表示完全没有必要，其实在跑SPFA的过程中，我们就可以随便把这些问题解决掉。
1、判0环
判0环和判负环其实差不多，只需要在SPFA中加一个判断即可，但是，由于此题卡时间卡得很紧，所以我们机房某大佬教了我卡带，这样判0环听说可以快很多。
if(dis[v]>=dis[u]+cost[i])
注意：SPFA这里需要把'>'改成">=",不然判不了0环
剩下的判0环方法就和判负环差不多,如果还不明白可以看代码。（另外提供一种判0环方式，把0边全部抽出来，然后判环，拓扑什么的）
2、确定dp更新顺序
这个其实也很简单，我们不难发现，其实只有0边两个点的顺序需要确定更新顺序，其他只需要按dis从小到大的顺序更新就可以了。于是我们在SPFA中加一个更新就可以了。
if(id[v]<id[u]+1)id[v]=id[u]+1;
这样即可确定dp更新顺序。dp前先按dis为第一关键字，id为第二关键字排序即可。
3、dp
额……，讲了怎么久的dp更新顺序，可能你们还不懂怎么dp吧，我的dp方法和Kelin大佬的一样，都是f[i][j]表示1至i的路径中，小于等于dis[i]+j的路径数。
转移也很简单，只要(dis[u]+j+(u至v的长度)-dis[v]<=K)
那么就将f[v][dis[u]+j+(u至v的长度)-dis[v]]+=f[u][j];
最后记得取膜蛤！dp的更新顺序记得按关键字排序啊。
还有，本蒟蒻由于dp学得不是很好，所以讲得如果不懂的话，可以看代码或者Kelin大佬讲的，我觉得他dp讲得比我好啊QAQ。
for(int k=0;k<=kk;k++) //dp
{
for(int j=1;j<=n;j++)
{
int u=a[j].pos,d=dis[u];
if(d>=inf)continue; //小剪枝
for(int i=head[u];i!=-1;i=Next[i])
{
int v=to[i];
if(cost[i]-dis[v]+d+k<=kk) //如果当前到v的状态的花费小于kk就更新
{
f[v][cost[i]-dis[v]+d+k]+=f[u][k]; //更新
f[v][cost[i]-dis[v]+d+k]%=mod; //记得取mod
}
}
}
} dp代码如上，还是比较好想到的呢。
好了那么思路也就差不多了，总体的难度其实不是很大，不过这样写的时间复杂度会比用拓扑的高，毕竟在找0环的时候比较耗时间，但是方法肯定是没问题的，接下来来看全部代码吧。
AC代码：
#include<bits/stdc++.h>
#define maxm 800000
#define maxn 400000
#define inf 20010100
using namespace std;
int cnt,from[maxm],to[maxm],cost[maxm],Next[maxm],head[maxm],cont[maxm],cb[maxn],id[maxn];//嗯，定义有点丑蛤
int dis[maxn],vis[maxn],f[maxn][65],ans;
int n,m,x,y,z,mod,kk;
struct kkk{
int dis,id,pos;
}a[maxn];
queue<int>q;
int cmp(kkk a,kkk b){ //排序操作
if(a.dis==b.dis)return a.id<b.id; //记得以dis为第一关键字哦~~~,id为第二关键字
else return a.dis<b.dis;
}
bool SPFA(int S){ //SPFA求最短路
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0,id[i]=0;
vis[S]=1;q.push(S);dis[S]=0;
int sum=0; //上面为初始化
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=0;
sum+=cb[u]+1;if(sum>2000000)return false; //卡带判0环
for(int i=head[u];i!=-1;i=Next[i])
{
int v=to[i];
if(dis[v]>=dis[u]+cost[i])
{
if(++cont[v]>=n)return false; //当然普通判0环也少不了
dis[v]=dis[u]+cost[i];
if(id[v]<id[u]+1)id[v]=id[u]+1; //id确定0边两个端点的更新顺序
if(vis[v]==0)
{
vis[v]=1;
q.push(v);
}
}
}
}
return true;
}
void add(int x,int y,int z){ //建边
cnt++;
cost[cnt]=z;cb[x]++;
from[cnt]=x;to[cnt]=y;
Next[cnt]=head[x];head[x]=cnt;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(head,-1,sizeof(head)); //初始化{
memset(cont,0,sizeof(cont));ans=0;
memset(a,0,sizeof(a));cnt=0; //}初始化
scanf("%d%d%d%d",&n,&m,&kk,&mod); //输入{
for(int i=1;i<=m;i++)
scanf("%d%d%d",&x,&y,&z),add(x,y,z);//}输入
bool flag=SPFA(1); //SPFA跑最短路
if(flag==false) //随便判0环
{printf("-1\n");continue;}
//***********************以上为基本操作-分界线-以下为dp求解***********************
for(int i=1;i<=n;i++)a[i].pos=i,a[i].dis=dis[i],a[i].id=id[i]; //dp的初始化
sort(a+1,a+n+1,cmp); //进行排序
//f[i][j]表示1至i的路径中，小于等于dis[i]+j的路径数
memset(f,0,sizeof(f));f[1][0]=1;//dp初始化
for(int k=0;k<=kk;k++) //dp
{
for(int j=1;j<=n;j++)
{
int u=a[j].pos,d=dis[u];
if(d>=inf)continue; //小剪枝
for(int i=head[u];i!=-1;i=Next[i])
{
int v=to[i];
if(cost[i]-dis[v]+d+k<=kk) //如果当前到v的状态的花费小于kk就更新
{
f[v][cost[i]-dis[v]+d+k]+=f[u][k]; //更新
f[v][cost[i]-dis[v]+d+k]%=mod; //记得取mod
}
}
}
}
for(int i=0;i<=kk;i++)
ans+=f[n][i],ans%=mod; //最后统计答案
printf("%d\n",ans);
}
} 
京公网安备 11010502036488号