Description
策策同学特别喜欢逛公园。公园可以看成一张 \(N\) 个点 \(M\) 条边构成的有向图，且没有 自环和重边。其中 \(1\) 号点是公园的入口， \(N\) 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从 \(1\) 号点进去，从 \(N\) 号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 \(1\) 号点 到 \(N\) 号点的最短路长为 \(d\) ，那么策策只会喜欢长度不超过 \(d+K\) 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗?
为避免输出过大，答案对 \(P\) 取模。
如果有无穷多条合法的路线，请输出 \(-1\)。
\(N\le 10^5,M\le 2\times 10^5,K\le 50\)。
Solution
\(K\) 的范围较小，枚举 \(i\) 表示额外长度。
先求出 \(1\) 到每个点的最短路 \(dis\)。设 \(f_{x,v}\) 表示到节点 \(x\) 额外长度为 \(v\) 的方案数。在反向图上遍历。若点 \(x\) 可以从点 \(y\) 走到，则有转移 \(f_{x,v}=\sum f_{y,v-(dis_y+z-dis_x)}\)。其中 \(dis_y+z-dis_x\) 是走这条路所需要的额外长度。
当有 \(0\) 环就存在无穷多条合法路线。而有 \(0\) 环意味着可能在求 \(f_{x,v}\) 时又走回了 \(f_{x,v}\) 这个状态。因此可以记录每个状态 \(\{x,v\}\) 是否在待处理的栈中。若 \(\{x,v\}\) 二次入栈则说明存在 \(0\) 环。
Code
#include<queue>
#include<cstdio>
#include<cstring>
#define N 100005
#define M 200005
#define K 55
#define inf 0x3f3f3f3f
using namespace std;
int T,n,m,mod,k,tot,ans,dis[N],f[N][K];
bool bj[N],bz[N][K];
struct edg
{
int tot=0,to[M],next[M],head[N],val[M];
void add(int x,int y,int z) {to[++tot]=y;val[tot]=z;next[tot]=head[x];head[x]=tot;}
}a,_a;
struct node
{
int x,dis;
bool operator>(const node& x) const {return dis>x.dis;}
};
priority_queue<node,vector<node>,greater<node>> q;
void dij()
{
memset(dis,inf,sizeof(dis));
memset(bj,false,sizeof(bj));
dis[1]=0;q.push((node){1,0});
while (!q.empty())
{
int x=q.top().x;q.pop();
if (bj[x]) continue;
bj[x]=true;
for (int i=a.head[x];i;i=a.next[i])
{
int y=a.to[i],z=a.val[i];
if (dis[y]>dis[x]+z)
{
dis[y]=dis[x]+z;
if (!bj[y]) q.push((node){y,dis[y]});
}
}
}
}
int dfs(int x,int rest)
{
if (rest<0||rest>k) return 0;
if (bz[x][rest])//二次入栈
{
bz[x][rest]=false;
return -1;
}
if (f[x][rest]!=-1) return f[x][rest];
bz[x][rest]=true;//入栈
int res=0;
for (int i=_a.head[x];i;i=_a.next[i])
{
int y=_a.to[i],z=_a.val[i];
int s=dfs(y,rest-(dis[y]+z-dis[x]));
if (s==-1) {bz[x][rest]=false;return -1;}
res=(res+s)%mod;
}
bz[x][rest]=false;//出栈
if (x==1&&rest==0) res++;//走到了起点
return f[x][rest]=res;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d%d",&n,&m,&k,&mod);
for (int i=1;i<=m;++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a.add(x,y,z);
_a.add(y,x,z);
}
dij();
memset(f,-1,sizeof(f));
memset(bz,false,sizeof(bz));
bool flag=true;ans=0;
for (int i=0;i<=k;++i)
{
int res=dfs(n,i);
if (res!=-1) ans=(ans+res)%mod;
else {flag=false;break;}
}
if (!flag) printf("-1\n");
else printf("%d\n",ans);
a.tot=_a.tot=0;
for (int i=1;i<=n;++i)
a.head[i]=_a.head[i]=0;
}
return 0;
}