[NOIP2017]逛公园 最短路图 拓扑序DP

～～～题面～～～

题解：

　　挺好的一道题。

　　首先我们将所有边反向，跑出n到每个点的最短路，然后f[i][j]表示从i号节点出发，路径长比最短路大j的方案数。

　　观察到，如果图中出现了0环，那么我们可以通过在环上走无数次来获得无数条不同路径，因此这就无解了。

　　如果没有0环，当且仅当这张图的最短路图是一个DAG(可以画图思考一下)，因为如果没有0环，而最短路图中出现了环，那么意味着你可以无数次以最短路到达同一个点，而不增加路径长，这显然是不可能的，同理，如果有0环，那么最短路图中就会出现环。

　　因此我们判断不合法只需要对图进行一遍拓扑排序，如果不能将所有点都加入队列的话，就是出现了环，那么就输出-1.

　　否则的话我们就按照拓扑序DP。

　　从感性的角度上来说，，，我们需要先获取离终点近的DP值才能更新里终点远的DP值。所以要按拓扑序DP（具体证明之类的我也不会）

　　DP的时候要先枚举比最短路长多少，因为DP时要通过原图转移，所以一个离终点近的点也可能会利用到离终点远的点，而DP的转移显然要依赖于用来更新其他点的值要 在被需要之前 更新完。

　　所以先枚举点是不对的，因为这样没有明确的需要与被需要关系，也可以认为是在一个环上互相转移了。

　　但是观察比最短路长多少这个条件，它是有明确的需要与被需要关系的，对于f[i][j]而言，j大的要利用j小的转移，j小的不可能用j大的转移，因为没有负边，所以这就避免了“环”的出现，于是可以保证DP转移合法。

#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 100100
#define ac 202000
#define LL long long

int n, m, k, p, T;
int in[AC], dis[AC];
int q1[ac], head, tail;
LL f[AC][60];
bool z[AC];

struct node{
    int dis, x;
};

struct cmp{
    bool operator() (node a, node b){
        return a.dis > b.dis;
    }
};

priority_queue<node, vector<node>, cmp> q;

struct road{
    int Head[AC], date[ac], Next[ac], len[ac], tot;
    
    inline void init()
    {
        memset(Head, 0, sizeof(Head));
        tot = 0;
    }
    
    inline void add(int f, int w, int S){
        date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, len[tot] = S;
    }    
}E1, E2, E3;

int read()
{
    int x = 0;char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

inline void up(LL &a, LL b)
{
    a += b;
    if(a > p) a -= p;
}

void pre()
{
    int a, b, c;
    E1.init(), E2.init(), E3.init();
    memset(f, 0, sizeof(f));
//    memset(in, 0, sizeof(in));
    memset(z, 0, sizeof(z));
    head = tail = 0;
    n = read(), m = read(), k = read(), p = read();
    for(R i = 1; i <= m; i ++)
    {
        a = read(), b = read(), c = read();
        E1.add(b, a, c), E3.add(a, b, c);
    }
    memset(dis, 127, sizeof(dis));
    dis[n] = 0, q.push((node){0, n});
}

void spfa()
{
    int x, now;
    while(!q.empty())
    {
        x = q.top().x, q.pop();
        while(z[x] && !q.empty()) x = q.top().x, q.pop();
        if(z[x]) break;
        z[x] = true;
        for(R i = E1.Head[x]; i; i = E1.Next[i])
        {
            now = E1.date[i];
            if(dis[now] > dis[x] + E1.len[i])
            {
                dis[now] = dis[x] + E1.len[i];
                q.push((node){dis[now], now});
            }    
        }
    }
}

void tsort()
{
    int x, now;
    while(head < tail)
    {
        x = q1[++head];
        for(R i = E2.Head[x]; i; i = E2.Next[i])
        {
            now = E2.date[i], --in[now];
            if(!in[now]) q1[++tail] = now;
        }
    }
}

void build()
{
    int now;
    for(R i = 1; i <= n; i ++)
    {
        for(R j = E1.Head[i]; j; j = E1.Next[j])
        {
            now = E1.date[j];
            if(dis[now] == dis[i] + E1.len[j])
                E2.add(i, now, E1.len[j]), ++ in[now];
        }
        //f[i][0] = 1; 
    }
    f[n][0] = 1;
    for(R i = 1; i <= n; i ++) 
        if(!in[i]) q1[++tail] = i;
    tsort();
}

void getans()
{
    if(tail < n) 
    {
        memset(in, 0, sizeof(in));
        printf("-1
"); 
        return ;
    }
    int now, x;
    for(R i = 0; i <= k; i ++)
    {
        for(R j = 1; j <= n; j ++)
        {
            x = q1[j];
            for(R l = E3.Head[x]; l; l = E3.Next[l])
            {
                now = E3.date[l];
                int t = E3.len[l] - dis[x] + dis[now];//获取现在新增的路径长度
                if(i - t >= 0) up(f[x][i], f[now][i - t]);
            }
        }
    }
    LL ans = 0;
    for(R i = 0; i <= k; i ++) up(ans, f[1][i]);
    printf("%lld
", ans);
}

void work()
{
    T = read();
    while(T --)
    {
        pre();
        spfa();
        build();
        getans();
    }
}

int main()
{
    freopen("in.in", "r", stdin);
    work();
    fclose(stdin);
    return 0;
}