邻接表：

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

/*
  题意总结：
  给定 n 个地窖（编号 1~n），每个地窖中有一定数量的地雷。
  连接关系为有向边 xi → yi，且 xi < yi（无环 DAG）。
  目标：选择一条从任意起点出发、顺着有向边往下走的路径，
        使得路径上地雷总数最大，并输出路径顺序和最大值。
*/

/*
  DP 定义：
  dp[i] 表示「以第 i 个地窖为终点」所能挖到的地雷总数的最大值。
  转移方程：
      dp[i] = max( dp[j] + w[i] )，其中存在边 j → i。
  初始化：
      dp[i] = w[i]（即只挖自己，不依赖其他地窖）
*/

void print_path(int k, const vector<int>& pre) {
    if (k == 0) return; // 递归终止条件
    print_path(pre[k], pre);
    if (pre[k] == 0)
        cout << k;
    else
        cout << "-" << k;
}

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

    int n;
    cin >> n; // 输入地窖个数

    vector<int> w(n + 1);    // w[i]: 第 i 个地窖的地雷数
    vector<int> dp(n + 1);   // dp[i]: 以 i 为终点的最大可挖地雷数
    vector<int> pre(n + 1);  // pre[i]: 记录 dp[i] 的最优前驱（用于路径重建）
    vector<vector<int>> g(n + 1); // 邻接表表示有向边

    // 输入每个地窖的地雷数
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        dp[i] = w[i]; // 初始状态：只挖当前地窖
    }

    // 输入有向边（xi → yi）
    while (true) {
        int x, y;
        cin >> x >> y;
        if (x == 0 && y == 0) break;
        g[y].push_back(x); // 存反向边方便 DP：找能到 y 的所有 j
    }

    int max_val = LLONG_MIN; // 当前最大挖雷总数
    int end_node = 0;        // 最优路径的终点

    // 因为 xi < yi，节点编号本身就是拓扑序，可直接顺序 DP
    for (int i = 1; i <= n; ++i) {
        // 枚举所有能到达 i 的前驱 j
        for (int j : g[i]) {
            if (dp[j] + w[i] > dp[i]) {
                dp[i] = dp[j] + w[i];
                pre[i] = j; // 记录最优前驱
            }
        }
        // 更新当前最大值与路径终点
        if (dp[i] > max_val) {
            max_val = dp[i];
            end_node = i;
        }
    }

    // 输出最优路径
    print_path(end_node, pre);
    cout << '\n' << max_val << '\n';

    return 0;
}

邻接矩阵写法：

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

/*
  题意（简述）：
  有 n 个地窖（1..n），每个地窖有地雷数 w[i]。有向边 xi->yi（且 xi<yi，无环）。
  从任意地窖出发，沿边一直向后挖（只能走一条路径），使路径上地雷总和最大。
  要输出：一条最优路径（用 '-' 连接）以及最大地雷数。

  DP 定义：
  dp[i] 表示「以 i 为终点」所能挖到的地雷总数的最大值。
  状态转移：
      dp[i] = max( dp[j] + w[i] )，对所有存在边 j->i 的 j。
  初始化：
      dp[i] = w[i]（只挖自己）
  路径重建：
      pre[i] 记录使 dp[i] 最优的前驱 j（若没有则为 0）。
*/

void print_path(int x, const vector<int>& pre) {
    if (x == 0) return;
    print_path(pre[x], pre);
    if (pre[x] == 0) cout << x;
    else cout << "-" << x;
}

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

    int n;
    if (!(cin >> n)) return 0;

    // 读入每个地窖的地雷数
    vector<long long> w(n + 1), dp(n + 1), pre(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        dp[i] = w[i];   // 初始化：只挖自己
    }

    // 邻接矩阵 g[u][v] = 1 表示 u -> v 有边（保证 u < v）
    vector<vector<int>> g(n + 1, vector<int>(n + 1, 0));
    while (true) {
        int x, y;
        if (!(cin >> x >> y)) return 0;
        if (x == 0 && y == 0) break;
        if (1 <= x && x <= n && 1 <= y && y <= n) {
            g[x][y] = 1;
        }
    }

    // 因为题目保证边都是从小编号指向大编号（拓扑序即 1..n），
    // 我们按 i 从小到大做 DP，枚举所有可能的前驱 j。
    long long best = LLONG_MIN;
    int end_node = 0;

    for (int i = 1; i <= n; ++i) {
        // 枚举所有 j，看是否存在 j->i 的边；若存在则尝试转移
        for (int j = 1; j <= n; ++j) {
            if (g[j][i]) { // j -> i
                if (dp[j] + w[i] > dp[i]) {
                    dp[i] = dp[j] + w[i];
                    pre[i] = j;        // 记录最优前驱
                }
            }
        }
        if (dp[i] > best) {
            best = dp[i];
            end_node = i;
        }
    }

    // 输出路径与最大值
    print_path(end_node, pre);
    cout << "\n" << best << "\n";
    return 0;
}