Luogu3953 NOIP2017逛公园（最短路+拓扑排序+动态规划）

　　跑一遍dij根据最短路DAG进行拓扑排序，按拓扑序dp即可。wa了三发感觉非常凉。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define ll long long

#define N 100010

#define M 200010

#define K 51

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T,n,m,k,P,p[N],d[N],from[M],f[N][K],Q[N],degree[N],t;

bool flag[N];

struct data{int to,nxt,len;

}edge[M];

struct data2

{

    int x,d;

    bool operator <(const data2&a) const

    {

        return d>a.d;

    }

};

priority_queue<data2> q;

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z;p[x]=t;}

void dijkstra()

{

    memset(d,,sizeof(d));d[]=;

    memset(flag,,sizeof(flag));

    q.push((data2){,});

    for (;;)

    {

        while (!q.empty()&&flag[q.top().x]) q.pop();

        if (q.empty()) break;

        data2 x=q.top();q.pop();flag[x.x]=;

        for (int i=p[x.x];i;i=edge[i].nxt)

        if (x.d+edge[i].len<d[edge[i].to])

        {

            d[edge[i].to]=x.d+edge[i].len;

            q.push((data2){edge[i].to,d[edge[i].to]});

        }

    }

}

bool topsort()

{

    memset(degree,,sizeof(degree));

    for (int i=;i<=m;i++)

    if (d[from[i]]+edge[i].len==d[edge[i].to]) degree[edge[i].to]++;

    int head=,tail=;for (int i=;i<=n;i++) if (!degree[i]) Q[++tail]=i;

    while (head<tail&&tail<n)

    {

        int x=Q[++head];

        for (int i=p[x];i;i=edge[i].nxt)

        if (d[x]+edge[i].len==d[edge[i].to])

        {

            degree[edge[i].to]--;

            if (!degree[edge[i].to]) Q[++tail]=edge[i].to;

        }

    }

    return tail<n;

}

int main()

{

    T=read();

    while (T--)

    {

        n=read(),m=read(),k=read(),P=read();

        t=;memset(p,,sizeof(p));

        for (int i=;i<=m;i++)

        {

            int x=read(),y=read(),z=read();

            from[i]=x;addedge(x,y,z);

        }

        dijkstra();

        if (topsort()) cout<<-<<endl;

        else

        {

            memset(f,,sizeof(f));f[][]=;

            for (int i=;i<=k;i++)

                for (int j=;j<=n;j++)

                {

                    int x=Q[j];

                    for (int y=p[x];y;y=edge[y].nxt)

                    {

                        int u=d[x]+edge[y].len-d[edge[y].to]+i;

                        if (u<=k) inc(f[edge[y].to][u],f[x][i]);

                    }

                }

            int ans=;

            for (int i=;i<=k;i++) inc(ans,f[n][i]);

            cout<<ans<<endl;

        }

    }

    return ;

}