跳转至

luogu3953 逛公园

题解

与路径统计很像的一道题。

设f[i][k]为起点到i点，距离与到其的最短路偏差（肯定大于d[i]，d[i]为1到i的最短路）为k时的路径数。

然后可以拓扑排序后按照k从小到大的对每个点进行dp:

设有边(u,v,w)，转移方程可以写成f[v][d[u]+w+k-d[v]]+=f[u][k]

顺序很重要，需要先枚举k然后再枚举点和边。

程序

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#define MAX_N 100007
#define MAX_M 200007
#define MAX_W 57

int N, M, K, P;
int head[MAX_N], nxt[MAX_M], to[MAX_M], dis[MAX_M], cap;
int d[MAX_N];
int deg[MAX_N], vertex[MAX_N], top;
int f[MAX_N][MAX_W];
bool inq[MAX_N];
std::queue<int> q;

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

void addEdge (int u, int v, int w) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
    dis[cap] = w;
}

void init () {
    memset(head, 0, sizeof(head));
    memset(deg, 0, sizeof(deg));
    memset(inq, false, sizeof(inq));
    memset(vertex, 0, sizeof(vertex));
    memset(f, 0, sizeof(f));
    cap = top = 0;
}

void spfa () {
    for (int i = 1;i <= N; ++i)
        d[i] = 2e9;
    d[1] = 0;
    q.push(1), inq[1] = true;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            if (d[to[i]] > d[x] + dis[i]) {
                d[to[i]] = d[x] + dis[i];
                if (!inq[to[i]])
                    q.push(to[i]), inq[to[i]] = true;
            }
        }
        inq[x] = false;
    }
}

inline bool topSort () {
    top = 0;
    for (int i = 1;i <= N; ++i)
        for (int j = head[i]; j; j = nxt[j])
            if (d[i] + dis[j] == d[to[j]])
                deg[to[j]]++;
    for (int i = 1;i <= N; ++i)
        if (!deg[i])
            vertex[++top] = i, q.push(i);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            if (d[to[i]] == d[x] + dis[i]) {
                deg[to[i]]--;
                if (!deg[to[i]]) {
                    vertex[++top] = to[i];
                    q.push(to[i]);
                }
            }
        }
    }
    return top == N;
}

void dp () {
    memset(f, 0, sizeof(f));
    f[1][0] = 1;
    for (int k = 0;k <= K; ++k) {
        for (int i = 1;i <= N; ++i) {
            int x = vertex[i];
            for (int j = head[x]; j; j = nxt[j]) {
                if (d[x] + dis[j] + k - d[to[j]] <= K) {
                    (f[to[j]][d[x] + dis[j] + k - d[to[j]]] += f[x][k]) %= P;
                }
            }
        }
    }
    int res = 0;
    for (int i = 0;i <= K; ++i)
        (res += f[N][i]) %= P;
    printf("%d\n", res % P);
}

void solve () {
    N = read(), M = read(), K = read(), P = read();
    int u, v, w;
    for (int i = 1;i <= M; ++i) {
        u = read(), v = read(), w = read();
        addEdge(u, v, w);
    }
    spfa();
    if (!topSort()) {puts("-1");return;}
    dp();
}

int main () {
    int T = read();
    while (T--) init(), solve();
    return 0;
}