题解 P3953 【逛公园】

tth37 · 2019-06-20 00:02:38 · 题解

一道看似图论实则可以用动态规划解决的题目。

朴素的状态定义：f[u][k]表示从1号节点走到u号节点，路径长度为k的方案总数。状态转移方程：

但是这样的状态定义有一个严重的问题：空间消耗过大。考虑到题目中给出的K值并不大，我们可以利用题目所要求的信息来优化状态设计。

优化后的状态定义：d[u]表示从1号节点走到u号节点的最短路长度，f[u][k]表示从1号节点走到u号节点，路径长度为d[u]+k的方案总数。

如此一来，状态所需的空间大大减少，但相应的状态转移略显复杂。不妨设f[u][k]状态可以由f[v][x]转移得到，则：

移项，得到：

因此，完整的状态转移方程如下：

我们最终要求的答案即为\sum_{i=0}^Kf[N][i]，用记忆化搜索实现即可。

代码如下：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;

struct Edge {int v, w;};
vector<Edge> G1[MAXN], G2[MAXN];

int T, N, M, K, P;
bool fail;
int f[MAXN][51];
int d[MAXN];
bool vis[MAXN];
bool ins[MAXN][51];

void Dijkstra() {
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, 1));
    d[1] = 0;
    while (q.size()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (vector<Edge>::iterator it = G1[u].begin(); it != G1[u].end(); it++) {
            int v = it->v, w = it->w;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                q.push(make_pair(-d[v], v));
            }
        }
    }
}

inline int dp(int u, int k) {
    if (k < 0) return 0;
    if (ins[u][k]){
        fail = 1;
        return 0;
    }
    if (f[u][k]) return f[u][k];
    ins[u][k] = 1;
    int ans = 0;
    for (vector<Edge>::iterator it = G2[u].begin(); it != G2[u].end(); it++) {
        int p = it->v, w = it->w;
        ans = (ans + dp(p, d[u] - d[p] + k - w))%P;
        if (fail == 1) return 0;
    }
    ins[u][k] = 0;
    return f[u][k] = ans;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d", &N, &M, &K, &P);
        for (register int i = 1; i <= M; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            G1[u].push_back((Edge){v, w});
            G2[v].push_back((Edge){u, w});
        }
        Dijkstra();
        dp(1, 0);
        f[1][0] = 1;
        int ans = 0;
        for (register int i = 0; i <= K; ++i) {
            ans = (ans + dp(N, i))%P;
        }
        if(fail == 1) puts("-1");
        else printf("%d\n", ans);
        fail = 0;
        memset(f, 0, sizeof(f));
        memset(ins, 0, sizeof(ins));
        for (register int i = 1; i <= N; ++i) {
            G1[i].clear(), G2[i].clear();
        }
    }
}