[noip2017-提高] 逛公园

GitHub跳转原题关系图返回列表

通过正反两次 Dijkstra 求出到起点和终点的最短路，结合 DFS 记忆化搜索统计额外代价不超过 K 的合法路径，利用栈来判断产生无穷方案的零环。

OJ: roj

题目 ID: 3650

难度:提高+/省选-

标签:图论最短路动态规划记忆化搜索

创建: 2026-10-10 09:25

更新: 2026-10-10 09:25

形式化题目

给定一个 $N$ 个点 $M$ 条边的有向图（没有自环和重边），边权均为非负数。设 1 号点到 $N$ 号点的最短路长度为 $d$ 。求从 1 号点到 $N$ 号点，路径长度不超过 $d + K$ 的路径条数。答案对 $P$ 取模。如果满足条件的路径有无穷多条，则输出 -1。输入包含多组数据（组数为 $T$ ）。

正解

思路

本题的 $K \le 50$ ，这是非常重要的提示，意味着我们可以在“比最短路多出来的长度”这一个维度上进行动态规划或记忆化搜索。

最短路预处理 首先，我们在正向图上以 1 为源点跑一次 Dijkstra，求出 1 到各点的最短路 d[u]。接着，在反向图上以 $N$ 为源点跑一次 Dijkstra，求出各点到 $N$ 的最短路 d_rev[u]。
状态设计 定义 dfs(u, j) 表示当前位于节点 u，且目前走过的路径比 d[u] 多出来的长度（偏移量）为 j。从当前状态出发，合法到达 $N$ 的路径总数。如果在搜索过程中，我们从 u 走向相邻的点 v（边权为 w），那么到达 v 时的相对偏移量会变成：
$next\_j = j + d[u] + w - d[v]$
只要 $next\_j \le K$ ，我们就递归搜索 dfs(v, next_j) 并累加其方案数。
零环与无穷解的判定 什么情况下会产生无穷多条路径？当且仅当图中存在一个总长度为 0 的环（即环上所有边权均为 0），且从 1 能走到这个环，且这个环能走到 $N$ 并在允许的额外长度 $K$ 之内。在我们的 DFS 记忆化搜索过程中，可以通过维护一个 in_stack[u][j] 布尔数组来判断。如果在同一次搜索路径中，我们再次访问到了相同的 (u, j) 状态，就意味着存在一个长度增量为 0 的环（即零环）。此时，如果这条包含零环的路径能够最终抵达 $N$ 并满足总长度约束，那么答案就是无穷大（即返回 -1）。
关键剪枝 由于不是所有零环都能产生有效的合法路径，为了避免误判（即陷入了一个死胡同里的零环），我们在 DFS 的最开始加入一个绝对距离的剪枝：如果 $d[u] + j + d\_rev[u] > d[N] + K$ ，说明即使接下来走绝对的最短路，总长度也超出了限制，直接返回 0。这就保证了所有被我们搜到的状态都具备合法走到 $N$ 的潜力。只要在这个剪枝之后发现零环，它必定能贡献出无穷多种有效路线。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98import sys
import heapq

sys.setrecursionlimit(2000000)

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
        
    t = int(data[0])
    idx = 1
    
    out = []
    
    for _ in range(t):
        n = int(data[idx])
        m = int(data[idx+1])
        k = int(data[idx+2])
        p = int(data[idx+3])
        idx += 4
        
        adj = [[] for _ in range(n + 1)]
        rev_adj = [[] for _ in range(n + 1)]
        
        for _ in range(m):
            u = int(data[idx])
            v = int(data[idx+1])
            w = int(data[idx+2])
            idx += 3
            adj[u].append((v, w))
            rev_adj[v].append((u, w))
            
        def dijkstra(start, graph):
            dist = [float('inf')] * (n + 1)
            dist[start] = 0
            pq = [(0, start)]
            
            while pq:
                d, u = heapq.heappop(pq)
                if d > dist[u]:
                    continue
                for v, w in graph[u]:
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
                        heapq.heappush(pq, (dist[v], v))
            return dist
            
        dist = dijkstra(1, adj)
        rev_dist = dijkstra(n, rev_adj)
        
        dp = [[-1] * (k + 1) for _ in range(n + 1)]
        in_stack = [[False] * (k + 1) for _ in range(n + 1)]
        has_infinity = False
        
        def dfs(u, j):
            nonlocal has_infinity
            
            if dist[u] + j + rev_dist[u] > dist[n] + k:
                return 0
                
            if in_stack[u][j]:
                has_infinity = True
                return 0
                
            if dp[u][j] != -1:
                return dp[u][j]
                
            in_stack[u][j] = True
            ways = 0
            
            if u == n:
                ways = 1
                
            for v, w in adj[u]:
                next_j = j + dist[u] + w - dist[v]
                if next_j <= k:
                    ways = (ways + dfs(v, next_j)) % p
                    if has_infinity:
                        in_stack[u][j] = False
                        return 0
                        
            in_stack[u][j] = False
            dp[u][j] = ways
            return ways
            
        ans = dfs(1, 0)
        
        if has_infinity:
            out.append("-1")
        else:
            out.append(str(ans))
            
    print('\n'.join(out))

if __name__ == '__main__':
    solve()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int to, weight;
};

int t, n, m, k, p;
vector<vector<Edge>> adj;
vector<vector<Edge>> rev_adj;
vector<int> dist;
vector<int> rev_dist;
int dp[100005][55];
bool in_stack[100005][55];
bool has_infinity;

void dijkstra(int start, const vector<vector<Edge>>& graph, vector<int>& d) {
    d.assign(n + 1, INF);
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

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

        if (cdist > d[u]) continue;

        for (const auto& edge : graph[u]) {
            int v = edge.to;
            int w = edge.weight;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}

int dfs(int u, int j) {
    if (dist[u] + j + rev_dist[u] > dist[n] + k) {
        return 0; // Pruning: Even with shortest path to end, it exceeds limit
    }
    
    if (in_stack[u][j]) {
        has_infinity = true;
        return 0;
    }
    
    if (dp[u][j] != -1) {
        return dp[u][j];
    }
    
    in_stack[u][j] = true;
    long long ways = 0;
    
    if (u == n) {
        ways = 1;
    }
    
    for (const auto& edge : adj[u]) {
        int v = edge.to;
        int w = edge.weight;
        int next_j = j + dist[u] + w - dist[v];
        
        if (next_j <= k) {
            ways = (ways + dfs(v, next_j)) % p;
            if (has_infinity) {
                in_stack[u][j] = false;
                return 0;
            }
        }
    }
    
    in_stack[u][j] = false;
    return dp[u][j] = ways;
}

void solve() {
    cin >> n >> m >> k >> p;
    adj.assign(n + 1, vector<Edge>());
    rev_adj.assign(n + 1, vector<Edge>());
    
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        rev_adj[v].push_back({u, w});
    }
    
    dijkstra(1, adj, dist);
    dijkstra(n, rev_adj, rev_dist);
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp[i][j] = -1;
            in_stack[i][j] = false;
        }
    }
    
    has_infinity = false;
    
    int ans = dfs(1, 0);
    
    if (has_infinity) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

复杂度

时间复杂度： 建图与两次 Dijkstra 的复杂度为 $\mathcal{O}(M \log N)$ 。记忆化搜索的状态数为 $N \times K$ ，每次搜索遍历其出边，所以总状态转移数为 $\mathcal{O}(M K)$ 。对于每组数据的时间复杂度为 $\mathcal{O}(M \log N + M K)$ 。总时间复杂度符合要求。
空间复杂度： 主要由 dp 数组决定，状态数为 $N \times K$ ，所以空间复杂度为 $\mathcal{O}(N K)$ 。在给定的范围内约 $20 \sim 30 \text{MB}$ ，完全可以通过。

总结

本题容易踩坑的地方在于：

死胡同里的零环： 如果只通过 DFS 栈内状态重复来判负环，可能将一个无法走到 $N$ （或者走不到终点且不合法的）零环错认为无穷多方案。因此引入 d_rev[u] 做合法性强剪枝是核心关键。
多组数据初始化： 图数组、DP 数组每次都必须完整清空，避免前面的数据影响当前局面的搜索。

[noip2017-提高] 逛公园

目录

形式化题目

正解

思路

代码

复杂度

总结