NOIP2017提高组.逛公园

题目

527. 逛公园

算法标签: 最短路, 记忆化搜索, 拓扑图, 递推

思路

如果直接计算设计状态表示$f[b][y]$, 从起点走到节点$b$, 并且走的路径长度是$y$的路线总数
考虑状态转移, 也就是枚举$b$节点的上一个点, 状态转移方程为$f[b][y]+=f[a][y-w]$, 但是点的数量是$10^5$量级, 算法时间复杂度是$O(N^2\times M)$, 时间复杂度来到了$10^5\times 10^5\times 2\times 10^5$会超时, 并且状态不能存在循环依赖

但是发现$K$的数据量级很小只有$50$, 对于点的第二维状态绝大部分是没意义的, 最多只会计算到$d[u]+k$, 也就是范围是$[d[u],d[u]+k]$, 只有$k+1$种状态, 可以将算法时间复杂度降低到$O(n\times (k+1))$级别

因此只需要存储有效状态, 只需要存储相对于$d[u]$的偏移量, 更新状态计算

上图是原状态表示, 但是因为新的$y$变为了偏移量, 因此新的$y^{\prime }=y+d[u]$, 因此状态计算更新为$d[u]+y-w_k$

对于状态$f[u][x]$

$$d[u]+x=d[v]+y-w_k$$

因此 $x=d[v]-d[u]+y-w_k$, 因为状态计算是递推的, 因此记忆化搜索进行状态转移更方便

如果有$0$环, 说明存在无穷多种方案, 绕一圈是一种方案, 两圈是一种方案, …
等价于记忆化搜索 等价于 记忆化搜索存在循环依赖(在本题中), 如果环与初始点不相连, 也是有解的, 但是在本题中是相连的

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 4e5 + 10, K = 60;

int n, m, k, mod;
int head[N], ed[M], ne[M], w[M], idx;
int d[N], f[N][K];
bool vis[N], in_stk[N][K];
bool flag;

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

void dijkstra() {
   
    memset(d, 0x3f, sizeof d);
    memset(vis, false, sizeof vis);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({
   0, 1});

    while (!q.empty()) {
   
        auto [dis, u] = q.top();
        q.pop();

        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; ~i; i = ne[i]) {
   
            // 跳过反向边
            if (i & 1) continue;
            int v = ed[i];
            if (d[u] + w[i] < d[v]) {
   
                d[v] = d[u] + w[i];
                q.push({
   d[v], v});
            }
        }
    }
}

int dfs(int u, int y) {
   
    if (in_stk[u][y]) {
   
        flag = true;
        return 0;
    }

    int &val = f[u][y];
    if (val != -1) return val;

    in_stk[u][y] = true;
    val = 0;
    if (u == 1 && y == 0) val = 1;

    for (int i = head[u]; ~i; i = ne[i]) {
   
        // 跳过正向边
        if (!(i & 1)) continue;
        int v = ed[i];
        // 计算剩余长度
        int x = d[u] + y - w[i] - d[v];
        if (x < 0 || x > k) continue;
        val = (val + dfs(v, x)) % mod;
        if (flag) return 0;
    }

    in_stk[u][y] = false;
    return val;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
   
        memset(head, -1, sizeof head);
        idx = 0;

        cin >> n >> m >> k >> mod;
        for (int i = 0; i < m; ++i) {
   
            int u, v, val;
            cin >> u >> v >> val;
            add(u, v, val);
            add(v, u, val);
        }

        dijkstra();

        memset(f, -1, sizeof f);
        memset(in_stk, false, sizeof in_stk);
        flag = false;

        int ans = 0;
        for (int i = 0; i <= k; ++i) {
   
            ans = (ans + dfs(n, i)) % mod;
            if (flag) break;
        }
        if (flag) ans = -1;
        cout << ans << "\n";
    }
    return 0;
}