洛谷P3953 [NOIP2017 提高组] 逛公园 题解

题目链接：P3953 [NOIP2017 提高组] 逛公园

题意：

策策同学特别喜欢逛公园。公园可以看成一张 $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 \le P \le 10^9,~1 \le a_i,b_i \le N\le 10^5,~1\le M\le2\times 10^5,~0\le K\le 50,~0 \le c_i \le 1000$

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

一道不知道欠了多少年的题，今天总算写掉了，不过看的题解好像不是主流解法

考虑设 $f(u,l)$ 表示 $1$ 号节点走到 $u$ 号节点，路径长度为 $l$ 的方案总数，则

$$f(u,l) = \sum_{(u, v) \in E} f(v,l-w(u, v))$$

接着考虑利用 $k \le 50$ 的性质来优化状态。记 $d_u$ 为 $1$ 到 $u$ 的最短路径长。

重新设 $f(u,l)$ 表示从 $1$ 走到 $u$ ，路径长度为 $d_u + l$ 的方案总数。

不妨设$f(u,l)$ 可以由 $f(v,x)$ 转移而来，则有 $d_v + x + w(u,v) = d_u + l$ ，移项可得

$$x = d_u - d_v + l - w(u,v)$$

因此转移方程如下：

$$f(u,l) = \sum_{(u, v) \in E} f(v,~d_u-d_v+l-w(u, v))$$

最终答案为 $\sum_{i = 0}^k f(n,i)$ 。因为这个方程比较不好顺序转移，所以用个记搜就好啦~

时间复杂度 $\mathcal{O}(nk + m \log m)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;
typedef long long ll;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define Fi first
#define Se second

priority_queue<pii> q; vector<pii> g1[N],g2[N];
int n,m,k,mod,d[N],f[N][55]; char ok=1,vis[N],ins[N][55];
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
void Dijkstra()
{
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    q.push({0, 1}), d[1] = 0;
    while(!q.empty())
    {
        int u = q.top().Se; q.pop();
        if(vis[u]) continue; vis[u] = 1;
        for(pii i : g1[u]) {
            int v = i.Fi, w = i.Se;
            if(d[v] > d[u] + w) { d[v] = d[u] + w; q.push({-d[v], v}); }
        }
    }
}
int dp(int u,int l)
{
    if(l < 0) return 0;
    if(ins[u][l]) { ok = 0; return 0; }
    if(f[u][l]) return f[u][l]; else ins[u][l] = 1;
    int res = 0;
    for(pii i : g2[u]) {
        int p = i.Fi, w = i.Se;
        add(res, dp(p, d[u] - d[p] + l - w));
        if(!ok) return 0;
    }
    ins[u][l] = 0; return (f[u][l] = res);
}
void solve()
{
    cin >> n >> m >> k >> mod;
    for(int i = 1, u,v,w; i <= m; i++) {
        cin >> u >> v >> w; g1[u].push_back({v, w}); g2[v].push_back({u, w});
    }
    Dijkstra(); dp(1, 0); f[1][0] = 1;
    int res = 0;
    for(int i = 0; i <= k; i++) add(res, dp(n,i));
    cout << (ok ? res : -1) << '\n';
    ok = 1; memset(f, 0, sizeof(f)); memset(ins, 0, sizeof(ins));
    for(int i = 1; i <= n; i++) { g1[i].clear(); g2[i].clear(); }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}