汤姆斯的天堂梦

题意

第 0 层只有一个起点星球。

之后一共有 N 层，每层有若干个星球。题目按层给出所有航线信息：当前层某个星球可以由上一层哪些星球飞来，以及每条航线的费用。

费用可能是正数，也可能是负数。要求从第 0 层出发，到达第 N 层任意一个星球，使总花费最小。

思路

最直接的想法是把所有可能路径都枚举出来，求其中最小值。

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：暴力枚举从第 0 层走到第 N 层的所有路径，只适合小数据对拍。

const int MAXN = 105;
const int MAXK = 105;
const long long INF = (1LL << 60);

int n;
int cnt[MAXN];
vector<pair<int, int> > pre[MAXN][MAXK];

// dfs(level, planet) 表示暴力枚举所有路径，求到达这一点的最小花费。
long long dfs(int level, int planet) {
    if (level == 0) {
        return 0;
    }

    long long best = INF;

    for (int i = 0; i < (int)pre[level][planet].size(); i++) {
        int from = pre[level][planet][i].first;
        int cost = pre[level][planet][i].second;
        best = min(best, dfs(level - 1, from) + cost);
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cnt[0] = 1;

    for (int level = 1; level <= n; level++) {
        cin >> cnt[level];
        for (int planet = 1; planet <= cnt[level]; planet++) {
            while (true) {
                int from;
                cin >> from;
                if (from == 0) {
                    break;
                }

                int cost;
                cin >> cost;
                pre[level][planet].push_back(make_pair(from, cost));
            }
        }
    }

    long long ans = INF;
    for (int planet = 1; planet <= cnt[n]; planet++) {
        ans = min(ans, dfs(n, planet));
    }

    cout << ans << '\n';
    return 0;
}

brute.cpp 的做法是：从最后一层某个星球出发，递归枚举它来自上一层哪些前驱，再一直追溯到第 0 层。

这个思路很直观，但瓶颈也很明显：如果每层分支很多，路径总数会指数增长，暴力只能做小数据。

关键观察是：图中的边只会从第 i-1 层连到第 i 层，所以整张图天然是 DAG。即使边权有负数，也不会有负环问题。

设 dp[i][j] 表示到达第 i 层第 j 个星球的最小花费，那么只需要看它所有上一层前驱：

dp[i][j] = min(dp[i-1][from] + cost)

也就是说，一个点的答案完全由上一层决定，直接按层转移即可。

样例转移表

这张表展示样例中每个星球的最小花费是怎样一层一层算出来的：

层数	星球	可选转移	最小花费
1	1	`起点 +15`	`15`
1	2	`起点 +5`	`5`
2	1	`15-5`, `5+10`	`10`
2	2	`15+3`	`18`
2	3	`5+40`	`45`
3	1	`10+1`, `18+5`, `45-5`	`11`
3	2	`18-19`, `45-20`	`-1`

从这张表可以看到，每个状态只依赖上一层已经求出的状态，所以按层 DP 就够了。最后一层有多个星球时，再统一取最小值，就是最终答案。

实现时还可以压缩掉第一维，只保留：

prev：上一层最优值
cur：当前层最优值

这样一边读输入一边转移，代码会更直接。

数组写法参考

如果想贴近传统 OI 写法，可以先看这个二维数组版本。它把每个星球的所有前驱先存下来，再统一按层转移。

DP 公式

设 $dp_{i,j}$ 表示到达第 $i$ 层第 $j$ 个星球的最小花费。第 $0$ 层只有虚拟起点：

dp_{0,1}=0

如果第 $i$ 层星球 $j$ 可以从上一层星球 $from$ 到达，费用为 $cost(from,j)$ ，则：

dp_{i,j}=\min_{from}\{dp_{i-1,from}+cost(from,j)\}

最后答案为最后一层所有星球中的最小值：

\min_j dp_{n,j}

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//Author by [Rainboy](https://github.com/rainboylvx)
//date: 2026-06-21 15:46:24

#include <bits/stdc++.h>
using namespace std;

int n;

struct node {
    int id;
    int spend;
};

// a[i][j][k] 表示 第i行的编号为j的星球 的第k个前驱
node a[105][105][105];
int cnta[105][105]; // cnta[i][j] 表示 第i行的编号为j的星球 前驱的数量

// f[i][j] = min(pre_ij + link-ij)
int f[105][105];
int k[105];

// int cnt[105][105];

void init(){
    std::cin >> n;

    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int level = i;
        std::cin >> k[i];

        // 编号为j的星球
        for(int j = 1 ;j <= k[i]; j++) {
            while(1) {
                int pre_id, spend;
                cin >> pre_id ;
                if( pre_id == 0) break;

                cnta[i][j]++;
                int now_tot = cnta[i][j];

                std::cin >> spend;
                a[level][j][ now_tot ].spend = spend;
                a[level][j][ now_tot ].id = pre_id ;

            }
        }

    }
}

int main (int argc, char *argv[]) {
    init();

    // memset(f,0x3f,sizeof(f));
    for(int i = 0;i <= 104 ;++i ) // i: 0->104
    {
        for(int j = 0;j <= 104 ;++j ) // j: 0->104
        {
            f[i][j] = 100 * 1000;
        }
    }
    f[0][1] = 0;

    // dp
    for(int i = 1 ; i<= n;i++) { // level
        for(int j = 1;j <= k[i];j++) { //编号为j的星球
            for(int cnt  = 1 ; cnt <= cnta[i][j] ;cnt++) {

                int spend = a[i][j][cnt].spend;
                int id = a[i][j][cnt].id;

                f[i][j] = min(f[i][j], f[i-1][id] + spend);
            }

            // printf("f[%d][%d] = %d\n",i,j,f[i][j]);

        }
    }

    int ans = 100 * 1000;
    for(int j = 1 ;j <= k[n];j++) {
        if( ans > f[n][j]) ans = f[n][j];
    }
    std::cout << ans << "\n";
    return 0;
}

公式解释：图按层展开后，当前层的星球只会从上一层星球到达。dp_{i,j} 枚举所有能连到它的上一层前驱，把前驱最小花费加上边费用取最小，就得到到达这个星球的最小花费。

代码

正式提交时可以使用下面这个版本。它一边读入一边转移，只保留上一层和当前层的最小花费。

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#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 60);

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    // 第 0 层只有一个起点星球，编号视为 1，初始花费为 0。
    vector<long long> prev(2, 0);

    for (int level = 1; level <= n; level++) {
        int k;
        cin >> k;

        vector<long long> cur(k + 1, INF);

        for (int planet = 1; planet <= k; planet++) {
            while (true) {
                int from;
                cin >> from;
                if (from == 0) {
                    break;
                }

                long long cost;
                cin >> cost;

                // 当前层的星球只会从上一层的某个星球转移过来。
                if (prev[from] < INF / 2) {
                    cur[planet] = min(cur[planet], prev[from] + cost);
                }
            }
        }

        prev = cur;
    }

    long long ans = INF;
    for (int i = 1; i < (int)prev.size(); i++) {
        ans = min(ans, prev[i]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设所有航线总数为 M。

时间复杂度： $O(M)$
空间复杂度： $O(K)$ ，其中 K 是单层最大星球数

总结

这题的核心不是负边，而是“分层且只往下一层走”这个结构。

一旦看出它是一张分层 DAG，问题就变成了最普通的按层动态规划：每个点从上一层所有前驱里取最小转移即可。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

样例转移表

数组写法参考

DP 公式

代码

复杂度

总结

一图流解析