题意解析

题目描述了荷兰商人在 Verweggistan 购买 pruls 的场景。每个工作坊的 pruls 按堆叠顺序出售（顶部优先），商人需按顺序购买某堆叠中的连续若干个盒子（从顶部开始），每个盒子的价格决定利润（售价 10 florins，利润 = 10 - 价格，若价格≥10 则利润≤0）。商人可从多个工作坊购买，但每堆只能选一个连续前缀（如某堆有 5 个盒子，可选买前 1、2、…、5 个）。目标是最大化总利润，并在利润最大时确定购买的 pruls 数量（若有多个数量对应同一最大利润，按升序输出，最多 10 个）。

解题思路

对于每个工作坊的堆叠，计算前$k$个盒子的利润之和（$k=0,1,...,b$，其中$k=0$表示不购买该堆叠）。 利润数组$profit[i][k]$：第i个工作坊购买前k个盒子的总利润（$k=0$时利润为 0，不购买）。 若前k个盒子中存在价格≥10 的情况，对应的利润可能为负，需判断是否选择该前缀（若总利润≤0，可选$k=0$，即不购买该堆叠）。状态定义：$dp[i][j]$表示前$i$个工作坊中购买$j$个 pruls 的最大总利润。 转移方程：对于第$i$个工作坊的每个可能前缀长度k（利润为p），更新$dp[i][j+k] = max(dp[i][j+k], dp[i-1][j] + p)$。遍历所有可能的 pruls 数量$j$，找到总利润等于最大利润的所有$j$，按升序输出（最多 10 个）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF = 0X3F3F3F3F;
const int maxn = 102;
int n, a, b;
int map[maxn][maxn];
bool vis[maxn];
int d[maxn];
struct edge {
    int to;
    int cost;
};
vector<edge> edges[maxn];
void SPFA(int s) {
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    queue<int> q;
    memset(d, INF, sizeof(d));
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        vis[v] = 0;
        for (int j = 0; j < edges[v].size(); j++) {
            edge e = edges[v][j];
            int u = e.to;
            int cost = e.cost;
            if (d[u] > d[v] + cost) {
                d[u] = d[v] + cost;
                if (!vis[u]) {
                    q.push(u);
                    vis[u] = 1;
                }
            }
        }
    }
}
int main() {
    while (cin >> n >> a >> b) {
        for (int i = 1; i <= n; i++) {
            int k;
            cin >> k;
            for (int j = 1; j <= k; j++) {
                int te;
                cin >> te;
                if (j == 1) {
                    edges[i].push_back({ te,0 });
                    map[i][te] = 0;
                }
                else {
                    map[i][te] = 1;
                    edges[i].push_back({ te,1 });
                }
            }
        }
        SPFA(a);
        if (d[b] == INF)
            cout << -1 << endl;
        else
            cout << d[b] << endl;
    }
    return 0;
}