NOIP2017逛公园问题终极指南：从Dijkstra到记忆化搜索的完整解析 | 算法竞赛必备技巧

一、问题理解与算法设计思路

逛公园问题要求计算从起点1到终点N的路径中，长度不超过最短路+K的路径数量。这是一个典型的图论计数问题，需要结合最短路算法和动态规划技巧。

核心算法选择：

1. Dijkstra算法：计算从起点到所有点的最短距离

2. 记忆化搜索：动态规划计算不超过K的额外路径数量

3. 反向图遍历：优化搜索过程

二、完整代码实现（带详细注释）

#include <bits/stdC++.h>
using namespACe std;

const int MAXN = 1e5 + 5;
const int MAXK = 55;

struct Edge { int to, w; };  // 边结构体，存储目标点和边权
vector<Edge> G[MAXN], rG[MAXN];  // 正向图和反向图
int dist[MAXN], dp[MAXN][MAXK];  // 最短路距离和记忆化数组
bool inStack[MAXN][MAXK], vis[MAXN];  // 检测环和访问标记
int T, N, M, K, P;  // 测试用例数、点数、边数、K值、模数

// Dijkstra算法计算最短路
void dijkstra(int s) {
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[s] = 0;
    pq.emplace(0, s);
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        
        for (auto &e : G[u]) {
            if (dist[e.to] > dist[u] + e.w) {
                dist[e.to] = dist[u] + e.w;
                pq.emplace(dist[e.to], e.to);
            }
        }
    }
}

// 记忆化搜索计算路径数量
int dfs(int u, int k) {
    if (k < 0) return 0;  // 超出K限制
    if (inStack[u][k]) return -1;  // 检测到环
    if (dp[u][k] != -1) return dp[u][k];  // 已计算过
    
    inStack[u][k] = true;  // 标记当前状态在栈中
    int res = (u == 1 && k == 0) ? 1 : 0;  // 基础情况
    
    for (auto &e : rG[u]) {  // 遍历反向图
        int delta = (dist[u] + k) - (dist[e.to] + e.w);  // 计算允许的额外距离
        if (delta < 0) continue;
        
        int t = dfs(e.to, delta);
        if (t == -1) return -1;  // 遇到环
        res = (res + t) % P;  // 累加结果
    }
    
    inStack[u][k] = false;  // 回溯
    return dp[u][k] = res;  // 记忆化存储结果
}

int solve() {
    dijkstra(1); // 计算从起点1的最短距离
    
    memset(dp, -1, sizeof(dp));
    memset(inStack, 0, sizeof(inStack));
    
    int ans = 0;
    for (int i = 0; i <= K; ++i) {  // 枚举所有可能的额外距离
        int t = dfs(N, i);
        if (t == -1) return -1;  // 存在无穷解
        ans = (ans + t) % P;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> T;
    while (T--) {
        cin >> N >> M >> K >> P;
        for (int i = 1; i <= N; ++i) {
            G[i].clear();
            rG[i].clear();
        }
        
        for (int i = 0; i < M; ++i) {  // 建图
            int a, b, c;
            cin >> a >> b >> c;
            G[a].emplace_back(Edge{b, c});
            rG[b].emplace_back(Edge{a, c});
        }
        
        cout << solve() << "\n";
    }
    return 0;
}

三、算法核心解析

1. Dijkstra预处理：

• 计算从起点到所有点的最短距离，为后续记忆化搜索提供基准

2. 记忆化搜索设计：

• dp[u][k]表示在点u，还能使用k的额外距离时的路径数

• 使用反向图进行搜索，优化效率

3. 关键公式：

• delta = (dist[u] + k) - (dist[e.to] + e.w)

• 计算从前驱节点转移时还能剩余的额外距离

4. 环路检测：

• 使用inStack数组检测可能导致无限解的情况

四、复杂度分析与优化

1. 时间复杂度：

• Dijkstra部分：O(M log N)

• 记忆化搜索部分：O(NK)

2. 空间优化：

• 可使用滚动数组优化dp空间

• 适当剪枝减少不必要的状态计算

3. 常见错误：

• 忘记处理环路情况

• 模数处理不正确

• 边界条件处理不全

参考：Dijkstra算法