(Des)
给定一个有向图,起点为(1),终点为(n),求和最短路相差不超过(k)的路径数量.有(0)边.如果有无数条,则输出(-1).
(nleq 10^5,kleq 50)
(Sol)
首先,有无数条边的情况一定是在与最短路相差不超过(k)的一条路上有(0)环.
先不考虑(0)边和(0)环,(get 70pts)做法:先跑一个最短路,(dis[i])表示从(1)到(i)的最短路径.记(f[u][k])表示从(1)到(u)路径长度不超过(dis[u]+k)的路径条数,(f[u][k])显然是转移到(f[v][dis[u]+k+w(u,v)-dis[v]]).转移顺序显然是从(dis)小的转移到(dis)大的,直接按(dis)从小到大的顺序.于是一个(O(NK))的(dp)就出炉了.
考虑正解.
首先看怎么判断无穷解.记(f_i)为(1)到(i)的最短路,(g_i)为(i)到(n)的最短路.判断无穷解:先把所有可行的(0)边拎出来,再看它们是不是组成了环.一条边((i,j))可行当且仅当(f_i+g_j+wleq f_n+k).于是这里就可以简单判断了.
接下来仍然是(dp),但是因为(0)边的存在所以并不能直接按(dis)从小到大的顺序转移,我们需要另外一种方法来确定(0)边两个端点的转移顺序.考虑把所有可行的(0)边的两个端点拎出来,然后拓扑排序.最后对于所有的点,只需要按照(f)为第一关键字,拓扑排序排出来的顺序为第二关键字排序,按照这个顺序更新即可.
其实还有更加简单的记忆化搜索的写法:
(dfs(u,res))表示已经从(1)号结点跑到(u)结点,还有可以比最短路多走(res)的长度,走到(n)结点的方案数.显然这里需要跑一个反向最短路(dis).答案是(sum dfs(v,res-(dis_v+w-dis_u))).记忆化一下即可.
怎么判断(0)环呢?只需要记一个(stk_{u,res})表示在搜索树中当前结点的祖先结点们有没有出现过这个状态,如果有,那么就一定有(0)环.
我永远喜欢记搜!
对了,还看到一个非常神仙的分层图求法.在这里.
(Code)
#include<bits/stdc++.h>
#define il inline
#define Ri register int
#define go(i,a,b) for(Ri i=a;i<=b;++i)
#define yes(i,a,b) for(Ri i=a;i>=b;--i)
#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
#define inf 2147480000
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define sc second
using namespace std;
il int read()
{
Ri x=0,y=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*y;
}
const int N=1e5+5;
int n,m,k,p,b[N],ct,dis[N],as,rem[N][55];
bool fl,stk[N][55];
priority_queue<pr>q;
struct nd{int v,w,nt;}a[N*2];
struct ed{int u,v,w;}e[N*2];
il void add(Ri u,Ri v,Ri w){a[++ct]=(nd){v,w,b[u]};b[u]=ct;}
il void inc(Ri &x,Ri y){x+=y;if(x>=p)x-=p;}
il void dijkstra()
{
go(i,1,n-1)dis[i]=inf;
dis[n]=0;q.push(mp(0,n));
while(q.size())
{
Ri u=q.top().sc,d=-q.top().fi;q.pop();
if(d>dis[u])continue;
e(i,u)
{
Ri v=a[i].v,w=a[i].w;
if(d+w<dis[v]){dis[v]=d+w;q.push(mp(-dis[v],v));}
}
}
}
il int dfs(Ri u,Ri res)
{
if(stk[u][res]){fl=1;return 0;}
if(rem[u][res])return rem[u][res];
stk[u][res]=1;Ri ret=0;
e(i,u)
{
Ri v=a[i].v,w=a[i].w,tmp=res-(dis[v]+w-dis[u]);
if(tmp>=0)inc(ret,dfs(v,tmp));
if(fl)return 0;
}
stk[u][res]=0;return rem[u][res]=ret;
}
int main()
{
Ri T=read();
while(T--)
{
n=read(),m=read(),k=read(),p=read(),as=0,fl=0;
go(i,1,m)e[i]=(ed){read(),read(),read()};
mem(b,0);ct=0;
go(i,1,m)add(e[i].v,e[i].u,e[i].w);
dijkstra();
mem(b,0);ct=0;
go(i,1,m)add(e[i].u,e[i].v,e[i].w);
mem(stk,0);mem(rem,0);rem[n][0]=1;
go(i,0,k){inc(as,dfs(1,i));if(fl)break;}
if(fl)printf("-1
");
else printf("%d
",as);
}
return 0;
}