当前位置：首页 > 提高组 > 2017年 NOIP 提高组逛公园（洛谷P3953）题解：代码解析与优化

2017年 NOIP 提高组逛公园（洛谷P3953）题解：代码解析与优化

3个月前 (06-16)

一、题目解读

2017年NOIP提高组“逛公园”题目（洛谷P3953）要求在有向图中计算从起点到终点满足特定条件的路径数量。题目难点在于处理路径长度限制与边权的关系，需要结合图论算法与动态规划思想，对算法效率有较高要求。

二、解题思路

采用“Dijkstra最短路 + 记忆化DFS”的解题策略：

1. 正向建图跑Dijkstra：计算每个点到起点的最短距离，用于后续路径长度的判断。

2. 反向建图处理边权：将原图反向存储，方便从终点递归搜索。

3. 记忆化搜索优化：用dp数组记录状态（节点+剩余步数），避免重复计算。

4. 剪枝条件：通过距离差判断无效路径，减少搜索分支。

三、解题步骤

1. 输入与初始化：读入图数据，清空存储结构。

2. 正向Dijkstra：以起点为源点，计算最短路径dist[]。

3. 反向建边：根据正向边权构建反向图rG[]，便于递归搜索。

4. 记忆化DFS：从终点开始，递归计算每个状态下的路径数，利用剪枝与取模操作优化。

5. 结果汇总：遍历所有剩余步数，累加合法路径数量。

四、代码与注释

#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]; // 最短距离，路径数量DP
bool inStack[MAXN][MAXK], vis[MAXN]; // 栈标记与访问标记
int T, N, M, K, P; // 测试次数、节点数、边数、步数限制、取模值

// Dijkstra算法计算单源最短路径
void dijkstra(int s) {
    // 初始化距离数组
    memset(dist, 0x3f, sizeof(dist));
    // 优先队列（小根堆）
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[s] = 0; // 起点距离为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]) { // 遍历u的出边
            if (dist[e.to] > dist[u] + e.w) { // 更新最短距离
                dist[e.to] = dist[u] + e.w;
                pq.emplace(dist[e.to], e.to); // 更新优先队列
            }
        }
    }
}

// 记忆化DFS计算路径数量
int dfs(int u, int k) {
    if (k < 0) return 0; // 步数不足直接返回0
    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; // 特殊边界：起点且步数为0时路径为1
    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); // 正向跑最短路
    memset(dp, -1, sizeof(dp)); // 初始化DP数组
    memset(inStack, 0, sizeof(inStack)); // 初始化栈标记
    int ans = 0; // 结果初始化
    for (int i = 0; i <= K; ++i) { // 遍历所有剩余步数
        int t = dfs(N, i); // 计算终点N的路径数
        if (t == -1) return -1; // 存在环则返回-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; // 边数据（省略输入代码，用户代码中未完整给出）
            // 正向边加入G，反向边加入rG
            // 例如：G[a].push_back({b, c}); rG[b].push_back({a, c});
        }
        int ans = solve(); // 调用求解函数
        if (ans == -1) cout << "有环" << endl;
        else cout << ans << endl;
    }
}

五、总结

该代码通过巧妙结合Dijkstra与记忆化搜索，高效解决了“逛公园”问题的路径计数。关键在于反向建边简化递归逻辑，并利用记忆化避免重复计算。算法时间复杂度为O(MlogM+NK)O(MlogM + NK)O(MlogM+NK)，适合竞赛场景。代码中剪枝优化与边界处理是解题核心，对动态规划与图论结合的题目具有参考价值。