洛谷题目传送门

又是一年联赛季。NOIP2017至此收官了。

这个其实是比较套路的图论DP了，但是细节有点恶心。

先求出\(1\)到所有点的最短路\(d1\)，和所有点到\(n\)的最短路\(dn\)。

设\(f_{i,j}\)表示\(i\)号点，所有与\(d1\)差距不超过\(j\)的路径条数。转移的时候肯定是从小到大枚举\(j\)，再枚举边转移。显然每条边都有一个\(\Delta\)值，为\(d1_x-d1_y+w\)，含义就是强制经过这条边的最短路长度相较于原最短路长度的增量。于是有转移式\(f_{x,j}\rightarrow f_{y,j+\Delta}\)。

显然上面的转移，要沿着最短路的方向转移，所以要按\(d1\)从小到大考虑每个点的出边。

没有\(0\)的边就可以直接开始做了，可偏偏就是有啊qwq。

首先来判无解，首先要有个\(0\)环，其次要有一条经过环的、长度小于等于\(d1_n+k\)的路径。考虑在所有\(0\)边的子图上拓扑排序，剩下未出队的肯定在环上，对剩下的点检查一遍有没有\(d1_x+dn_x\le d1_n+k\)的。

接下来，还别忘了处理被\(0\)边所连起来的点的转移顺序。这个时候如果剩下环肯定贡献不到答案，需要处理的就是一些DAG上的点的顺序了。显然来一组拓扑序就可以了，拓扑排序的时候顺便搞搞。转移顺序就用\(d1\)和拓扑序双关键字确定好了。

时间复杂度\(O(T((n+m)\log m+kn))\)

#include<bits/stdc++.h>

#define LL long long

#define RG register

#define R RG int

#define G if(++ip==ie)fread(ip=buf,1,SZ,stdin)

using namespace std;

const int SZ=1<<19,N=1e5+9,M=4e5+9;

int n,m,k,YL,p,he[N],re[N],ne[M],to[M],w[M],deg[N],q[N],d1[N],dn[N],o[N],ord[N],f[N][51];

bool vis[N];

struct Node{

    int d,x;

    inline bool operator<(Node a)const{

        return d>a.d||(d==a.d&&o[x]>o[a.x]);

    }

};

priority_queue<Node>Q;

char buf[SZ],*ie=buf+SZ,*ip=ie-1;

inline int in(){

    G;while(*ip<'-')G;

    R x=*ip&15;G;

    while(*ip>'-'){x*=10;x+=*ip&15;G;}

    return x;

}

inline void add(R&x,R y){

    if((x+=y)>=YL)x-=YL;

}

void dij(R*d,R*he,R x){//最短路

    memset(d+1,127,4*n);memset(vis+1,0,n);

    Q.push((Node){d[x]=0,x});

    while(!Q.empty()){

        x=Q.top().x;Q.pop();

        if(vis[x])continue;

        vis[x]=1;

        if(d==d1)ord[++p]=x;//记录转移顺序

        for(R y,i=he[x];i;i=ne[i])

            if(d[y=to[i]]>d[x]+w[i])

                Q.push((Node){d[y]=d[x]+w[i],y});

    }

}

int main(){

    for(R T=in();T;--T){

        n=in();m=in();k=in();YL=in();

        R x,y,t=0;

        for(R i=1;i<=m;++i){

            x=in(),y=in();//建双向边

            ne[i]=he[x];to[he[x]=i]=y;i+=m;

            ne[i]=re[y];to[re[y]=i]=x;i-=m;

            if(!(w[i]=w[i+m]=in()))++deg[y];

        }

        for(R i=1;i<=n;++i)//拓扑排序

            if(!deg[i])q[++t]=i;

        for(R h=0;h<=t;++h){

            o[x=q[h]]=h;

            for(R i=he[x];i;i=ne[i])

                if(!w[i]&&!--deg[to[i]])q[++t]=to[i];

        }

        dij(d1,he,1);dij(dn,re,n);

        for(R i=1;i<=n;++i)

            if(deg[i]&&d1[i]+dn[i]<=d1[n]+k){puts("-1");goto F;}

        for(x=1;x<=n;++x)//重赋边权为Δ

            for(R i=he[x];i;i=ne[i])

                w[i]+=d1[x]-d1[to[i]];

        f[1][0]=1;//DP开始

        for(R j=0;j<=k;++j)

            for(R i=1;i<=n;++i)

                if(f[x=ord[i]][j])

                    for(R i=he[x];i;i=ne[i])

                        if(j+w[i]<=k)add(f[to[i]][j+w[i]],f[x][j]);

        for(R i=x=0;i<=k;++i)add(x,f[n][i]);

        printf("%d\n",x);

      F:memset(he+1,0,4*n);memset(re+1,0,4*n);

        memset(o+1,0,4*n);memset(deg+1,0,4*n);memset(ord+1,0,4*n);

        memset(f+1,0,4*51*n);p=0;

    }

    return 0;

}