题目描述

策策同学特别喜欢逛公园。公园可以看成一张$$N$$个点$$M$$条边构成的有向图,且没有 自环和重边。其中1号点是公园的入口,$$N$$号点是公园的出口,每条边有一个非负权值, 代表策策经过这条边所要花的时间。

策策每天都会去逛公园,他总是从1号点进去,从$$N$$号点出来。

策策喜欢新鲜的事物,它不希望有两天逛公园的路线完全一样,同时策策还是一个 特别热爱学习的好孩子,它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到$$N$$号点的最短路长为$$d$$,那么策策只会喜欢长度不超过$$d + K$$的路线。

策策同学想知道总共有多少条满足条件的路线,你能帮帮它吗?

为避免输出过大,答案对$$P$$取模。

如果有无穷多条合法的路线,请输出$$-1$$。

输入输出格式

输入格式:

第一行包含一个整数 $$T$$, 代表数据组数。

接下来$$T$$组数据,对于每组数据: 第一行包含四个整数 $$N,M,K,P$$,每两个整数之间用一个空格隔开。

接下来$$M$$行,每行三个整数$$a_i,b_i,c_i$$,代表编号为$$a_i,b_i$$的点之间有一条权值为 $$c_i$$的有向边,每两个整数之间用一个空格隔开。

输出格式:

输出文件包含 $$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】

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

【测试数据与约定】

对于 100%的数据, $$1 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 1000$$。

数据保证:至少存在一条合法的路线。

题解

跑两次最短路+记忆化搜索

第一次最短路求出从起点到所有点的最短路

第二次建反图,跑出所有点的连通性(即在SPFA中是否进过队)

然后我们用$$dp[cur][res]$$表示当前跑到$$cur$$号点,还能跑的距离为$$res$$时的方案数

注意到只有存在零环时才会出现无数条路径的情况,那么我们记一个$$vis$$数组表示这个点访问过,如果重复访问一个点且剩余长度不变的话就是有零环

代码:

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int Maxv = 200010; 
const int INF = 0x6ffffff; 

int dp[Maxv][55], dist[Maxv], Head[Maxv], book[Maxv], limit, cnt, n, m, k, p; 
bool vis[Maxv][55], inq[Maxv]; 

struct Node {
    int v, w, next; 
} N[Maxv << 1], N2[Maxv << 1]; 

struct Node2 {
    int u, d; 
    
    bool operator < (const Node2 &tmp) const {
        return d > tmp.d; 
    }
}; 

inline char fgc() {
    static char buf[1 << 15], *p1 = buf, *p2 = buf; 
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 15, stdin), p1 == p2) ? EOF : *p1++; 
}

inline int read() {
    static int x, ch, f; 
    x = 0, f = 0, ch = fgc(); 
    while (ch < '0' || ch > '9') ch == '-' ? f = 1 : 0, ch = fgc(); 
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = fgc(); 
    return f ? -x : x;
}

inline void addEdge(int u, int v, int w) {
    cnt++; 
    N[cnt].v = v; 
    N[cnt].w = w; 
    N[cnt].next = Head[u]; 
    Head[u] = cnt; 
}

int Head2[Maxv], cnt2; 

inline void addEdge2(int u, int v, int w) {
    cnt2++; 
    N2[cnt2].v = v; 
    N2[cnt2].w = w; 
    N2[cnt2].next = Head2[u]; 
    Head2[u] = cnt2; 
}

inline void Dijkstra() {
    std::priority_queue<Node2> q; 
    q.push((Node2){1, 0}); 
    dist[1] = 0; 
    
    while (!q.empty()) {
        Node2 cur = q.top(); 
        q.pop(); 

        int u = cur.u, d = cur.d; 
        if (d != dist[u]) continue;

        for (int i = Head[u]; i; i = N[i].next) {
            int v = N[i].v; 

            if (dist[v] > dist[u] + N[i].w) {
                dist[v] = dist[u] + N[i].w; 
                q.push((Node2){v, dist[v]}); 
            }
        }
    }

    return; 
}

inline void SPFA() {
    std::queue<int> q; 
    q.push(n); 
    inq[n] = true; 

    while (!q.empty()) {
        int u = q.front(); 
        q.pop(); 

        for (int i = Head2[u]; i; i = N2[i].next) {
            int v = N2[i].v; 

            if (!inq[v]) {
                inq[v] = true;
                q.push(v); 
            }
        }
    }

    return; 
}

inline int DFS(int cur, int res) {
    if (res < 0) return 0; 
    else if (vis[cur][res]) return -INF; 
    else if (dp[cur][res] != -1) return dp[cur][res]; 
    else {
        vis[cur][res] = true; 
        int ans = 0; 
        
        if (cur == n) ans++; 

        for (int i = Head[cur]; i; i = N[i].next) {
            if (!inq[ N[i].v ]) continue; 

            int v = N[i].v, w = N[i].w, dis = dist[v] - dist[cur]; 
            int sum = DFS(v, res - (w - dis)); 

            if (sum == -INF) return -INF; 
            else (ans += sum) %= p; 
        }
        
        vis[cur][res] = false; 
        dp[cur][res] = ans % p; 
        
        return ans; 
    }
}

inline void Init() {
    cnt = cnt2 = 0; 
    memset(N, 0, sizeof(N)); 
    memset(N2, 0, sizeof(N2)); 
    memset(Head, 0, sizeof(Head)); 
    memset(Head2, 0, sizeof(Head2)); 
    memset(dist, 0x3f, sizeof(dist)); 
    memset(inq, false, sizeof(inq));
    memset(vis, false, sizeof(vis)); 
    memset(dp, -1, sizeof(dp)); 
}

int main() {
    int T = read(); 
    
    while (T--) {
        Init(); 
        n = read(); 
        m = read(); 
        k = read(); 
        p = read(); 

        for (int i = 1; i <= m; i++) {
            int u = read(); 
            int v = read(); 
            int w = read(); 
            addEdge(u, v, w); 
            addEdge2(v, u, w); 
        }

        Dijkstra(); 
        SPFA(); 
        
        int ans = DFS(1, k); 
        if (ans == -INF) puts("-1"); 
        else {
            printf("%d\n", ans); 
        }
        
    }

    return 0; 
}