题目描述
策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图，且没有 自环和重边。其中1号点是公园的入口，N号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从1号点进去，从N号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到N号点的最短路长为d，那么策策只会喜欢长度不超过d+K的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？
为避免输出过大，答案对P取模。
如果有无穷多条合法的路线，请输出−1。
输入输出格式
输入格式：
第一行包含一个整数 T, 代表数据组数。
接下来TT组数据，对于每组数据： 第一行包含四个整数 N,M,K,P，每两个整数之间用一个空格隔开。
接下来M行，每行三个整数ai,bi,ci，代表编号为ai,bi的点之间有一条权值为 ci的有向边，每两个整数之间用一个空格隔开。
输出格式：
输出文件包含 T 行，每行一个整数代表答案。
输入输出样例
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
说明
【样例解释1】
对于第一组数据，最短路为 33。 $1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5$ 为 33 条合法路径。
【测试数据与约定】
对于不同的测试点，我们约定各种参数的规模不会超过如下
| 1 | 5 | 5 | 10 | 0 | 否 |
| 2 | 5 | 1000 | 2000 | 0 | 否 |
| 3 | 5 | 1000 | 2000 | 50 | 否 |
| 4 | 5 | 1000 | 2000 | 50 | 否 |
| 5 | 5 | 1000 | 2000 | 50 | 否 |
| 6 | 5 | 1000 | 2000 | 50 | 是 |
| 7 | 5 | 100000 | 200000 | 0 | 否 |
| 8 | 3 | 100000 | 200000 | 50 | 否 |
| 9 | 3 | 100000 | 200000 | 50 | 是 |
| 10 | 3 | 100000 | 200000 | 50 | 是 |
对于 100%的数据, 1 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 10001≤P≤109,1≤ai,bi≤N,0≤ci≤1000。
数据保证：至少存在一条合法的路线。
------------------------------------------------------
在此衷心感谢rockdu～
还是本着避开DP的原则，这一次我们继续用骚操作的避开一波浓浓的DP味～～～～
以下摘录rockdu的原话加上我的一点点理解：
首先这道题关键的一步是找出T到所有点的最短路是多少，
虽然起点很多但是终点只有一个，我们从终点反着跑最短路，就可以求出所有的最优距离。
然后我们想，如果从S出发到达点u，距离误差已经超过了K，这时候会怎么样呢？
我们无力回天，因为即使用最优策略也只能让误差不增加
所以对于每一个点，我们只关心误差在K以内的方案数
这时候统计方案数需要用到一个技巧，叫拆点最短路
对于每一个原图中的点，我们把它都拆成K个点，第x个点表示到了点u时误差为x的状态，也就是说强行把原来的走到u这个状态细化了，现在每一个小点能更精确的表示需要的信息
再进一步思考，这个图一定是一个dag：因为边权不为0，误差一定增大
那么想象一下，如果把小点从平面的图中拉出来
形成一层一层的结构，每一层都是一个x，那么一定是只能从x小的层向x大的层流动
也就是不可能一个点误差是k走一圈回来误差仍然是k，整个层次图构成了dag
因此，统计dag上可以到达T的路径数就可以了，写一个记忆化搜索做到O(n) (我最后用的topsort+f[i]来解决这一个问题 topsort顺便用来判了-1的情况
如果有边权为0的，并且可以反向到达S正向到达T的环，那么有无限组方案
我觉得整个过程真的是妙妙啊....
同时要注意：
1.memset(first,0,sizeof(first));
2.根据新图的性质要把数组开到足够大
3.仔细品读建新图的过程
4.记得手写队列
以下代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 200100
#define ll long long
using namespace std;
int n,m,k,p;
ll ans;
struct node
{
int u,v,w,nxt;
}e[N*],g[N*];
int first[N],cnt;
void ade(int u,int v,int w)
{
e[++cnt].nxt=first[u]; first[u]=cnt;
e[cnt].u=u; e[cnt].v=v; e[cnt].w=w;
}
int fir[N*],cnnt;
void adde(int u,int v,int w)
{
g[++cnnt].nxt=fir[u]; fir[u]=cnnt;
g[cnnt].u=u; g[cnnt].v=v; g[cnnt].w=w;
}
void adeg(int u,int v)
{
g[++cnnt].nxt=fir[u]; fir[u]=cnnt;
g[cnnt].u=u; g[cnnt].v=v;
}
ll dis[N];
bool vis[N]; void spfa(int x)
{
queue<int>q;
memset(dis,0x3f,sizeof(dis));
memset(vis,true,sizeof(vis));
q.push(x);
dis[x]=;
while(!q.empty())
{
int u=q.front(); q.pop();
vis[u]=true;
for(int i=first[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(vis[v]==true)
{
q.push(v);
vis[v]=false;
}
}
}
}
}
ll dis2[N];
void spfa2(int x)
{
queue<int>q;
memset(dis2,0x3f,sizeof(dis));
memset(vis,true,sizeof(vis));
q.push(x);
dis2[x]=;
while(!q.empty())
{
int u=q.front(); q.pop();
vis[u]=true;
for(int i=fir[u];i;i=g[i].nxt)
{
int v=g[i].v;
if(dis2[v]>dis2[u]+g[i].w)
{
dis2[v]=dis2[u]+g[i].w;
if(vis[v]==true)
{
q.push(v);
vis[v]=false;
}
}
}
}
}
int get(int x,int y)
{
return (x-)*(k+)+y+;
}
int ru[N*];
void build_graph()
{
for(int i=;i<=m;i++)
{
int u=e[i].u,v=e[i].v,w=e[i].w;
int x=get(u,);
int y=get(v,dis[u]+w-dis[v]);
for(int j=dis[u];j+w+dis2[v]<=dis[n]+k;j++,x++,y++)
{ adeg(x,y); ru[y]++; }
}
}
ll sum,f[N*];
int q[N<<];
void topsort2()
{
int l = ,r=;
for(int i = ;i<=n*(k+);i++)
if(!ru[i]) q[++r]=i;
f[]=;
while(l<r)
{
int x=q[++l];
sum++;
for(int i=fir[x];i;i=g[i].nxt)
{
int v=g[i].v;
ru[v]--;
if(!ru[v]) q[++r]=v;
f[v]+=f[x];
f[v] = f[v]>p ? f[v]-p : f[v];
}
}
}
void pre()
{
memset(first,,sizeof(first));
memset(fir,,sizeof(fir));
memset(f,,sizeof(f));
memset(ru,,sizeof(ru));
sum=ans=cnnt=cnt=;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
pre();
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
ade(x,y,z); adde(y,x,z);
}
spfa();
spfa2(n);
memset(fir,,sizeof(fir));
cnnt=;
build_graph();
topsort2();
int num=(k+)*n;
if(sum<num) printf("-1\n");
else
{
for(int i=;i<=k;i++)
ans=(ans+f[get(n,i)])%p;
printf("%lld\n",ans);
}
}
return ;
}
/*
1
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
*/
我爱rockdu