Description

策策同学特别喜欢逛公园。公园可以看成一张n个点m条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，n号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。策策每天都会去逛公园，他总是从1号点进去，从n号点出来。策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果1号点到n号点的最短路长为e，那么策策只会喜欢长度不超过e + k的路线。策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？为避免输出过大，答案对p取模。如果有无穷多条合法的路线，请输出−1。

Input

输入文件名为 park.in 。
第一行包含一个整数 T, 代表数据组数。
接下来T组数据，对于每组数据：
第一行包含四个整数 n,m,k,p，每两个整数之间用一个空格隔开。
接下来N行，每行三个整数 bi,ci,di ， 代表编号为 bi,ci 的点之间有一条权值为 di 的有向边，每两个整数之间用一个空格隔开。

Output

输出文件包含 T 行，每行一个整数代表答案。

Sample Input

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

Sample Output

3
-1

样例说明：

对于第一组数据，最短路为 3。
1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 3 条合法路径。

Data Constraint

对于不同的测试点，我们约定各种参数的规模 不会超过如下

对于 100%的数据, 1≤p≤109,1≤bi,ci≤n,0≤di≤1000 。

Solution

• 这题如果直接DP的话，会发现有后效性，则会重复统计答案。

• 但看到 k≤50 ，很小，于是我们考虑拆点。

• 先做一次 Spfa ，设 1 到 i 号点的最短路为 dis[i] 。

• 之后把每个点拆成 k+1 个点，分别对应到这个点时的路径长 j−dis[i] 的值。

• 由于这个值的范围只在 [0,k] 之间，

• 那么我们对于开始时的有向边的两个点拆点，并进行进行连接。

• 这样我们就构成了一个拓扑图，跑一遍拓扑排序即可。

• 当跑完后发现并没有遍历所有点，则直接输出 -1 即可。

• 而且这题还要卡卡常，发现连边时连接了很多无用点，拖慢了拓扑排序的速度。

• 于是我们考虑倒着做一遍 Spfa （从 n 开始）。

• 当一个点 dis[i]+dis1[i]>dis[n]+k 时，说明这个点就没用了，不需要从它连边出去。

• 时间复杂度 O(T∗M∗K) 。

Code

#include<cstdio> #include<cstring> #include<cctype> using namespace std; const int N=1e5+1,K=51; int n,m,k,p,tot,ans=0; int first[N],next[N<<1],en[N<<1],w[N<<1]; int first1[N*K],next1[N*K<<1],en1[N*K<<1],d[N*K]; int q[N<<6],dis[N],dis1[N],u[N<<1],v[N<<1],t[N<<1],f[N*K]; bool bz[N]; inline int read() {int X=0,w=1; char ch=0;while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void insert1(int x,int y) {next1[++tot]=first1[x];first1[x]=tot;en1[tot]=y;d[y]++; } inline int get(int x,int y) {return (x-1)*(k+1)+y+1; } int main() {int T=read();while(T--){n=read(),m=read(),k=read(),p=read();memset(first,tot=0,sizeof(first));for(int i=1;i<=m;i++){u[i]=read(),v[i]=read(),t[i]=read();insert(u[i],v[i],t[i]);}memset(dis,60,sizeof(dis));int l=dis[1]=0,r=q[1]=1;while(l<r){int x=q[++l];bz[x]=false;for(int i=first[x];i;i=next[i])if(dis[x]+w[i]<dis[en[i]]){dis[en[i]]=dis[x]+w[i];if(!bz[en[i]]) bz[q[++r]=en[i]]=true;}}memset(first,tot=0,sizeof(first));for(int i=1;i<=m;i++) insert(v[i],u[i],t[i]);memset(dis1,60,sizeof(dis1));l=dis1[q[r=1]=n]=0;while(l<r){int x=q[++l];bz[x]=false;for(int i=first[x];i;i=next[i])if(dis1[x]+w[i]<dis1[en[i]]){dis1[en[i]]=dis1[x]+w[i];if(!bz[en[i]]) bz[q[++r]=en[i]]=true;}}memset(first1,tot=0,sizeof(first1));memset(d,0,sizeof(d));for(int i=1;i<=m;i++){int x=get(u[i],0),y=get(v[i],dis[u[i]]+t[i]-dis[v[i]]);for(int j=dis[u[i]];j+t[i]+dis1[v[i]]<=dis[n]+k;j++,x++,y++) insert1(x,y);}int num=(k+1)*n,sum=0;l=r=ans=0;memset(f,0,sizeof(f));for(int i=1;i<=num;i++)if(!d[i]) q[++r]=i;f[1]=1;while(l<r){int x=q[++l];sum++;for(int i=first1[x];i;i=next1[i]){if(!--d[en1[i]]) q[++r]=en1[i];f[en1[i]]+=f[x];f[en1[i]]=f[en1[i]]>p?f[en1[i]]-p:f[en1[i]];}}if(sum<num) printf("-1\n"); else{for(int i=0;i<=k;i++) ans=(ans+f[get(n,i)])%p;printf("%d\n",ans);}}return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5475. 【NOIP2017提高组正式赛】逛公园的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。