【NOIP2017】逛公园 拆点最短路+拓扑(记忆化搜索

题目描述

策策同学特别喜欢逛公园。公园可以看成一张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 行，每行一个整数代表答案。

输入输出样例

输入样例#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

输出样例#1：

3
-1

说明

【样例解释1】

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

【测试数据与约定】

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

对于 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