洛谷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;
}