题意分析

题目背景

本题属于带约束的最短路径问题，描述探险家通过物品交换来降低迎娶酋长女儿所需金币数的过程。核心挑战在于处理等级限制下的最优交易策略。

核心规则

1. 等级限制：交易双方的等级差不得超过$M$。
   • 若酋长等级为$L_1$，则有效交易区间为$[L_1 - M, L_1 + M]$。
2. 交易方式：
   • 直接购买物品$i$的价格为$P_i$。
   • 可用物品$j$替代购买$i$，花费优惠价$V_{j→i}$。
3. 目标：以最低成本获得物品1（酋长的允诺）。

输入输出

• 输入：
  • $M$（等级限制），$N$（物品数量）。
  • 每个物品的$P_i$、等级$L_i$、替代品数量$X_i$及其对应的$T_j$和$V_j$。
• 输出：获取物品1的最低金币数。

解题思路

1. 图模型构建

• 节点：虚拟起点0（初始状态）和物品1~$N$。
• 边权：
  • $0→i$：直接购买成本$P_i$。
  • $j→i$：替代成本$V_{j→i}$。
• 约束：交易时，双方等级差$\leq M$。

2. 等级区间枚举

对每个可能的区间$[L, L+M]$（$L \in [L_1-M, L_1]$），执行Dijkstra算法：

3. Dijkstra算法

• 初始化：$dist[0] = 0$，其余为$+\infty$。
• 松弛操作：$$dist[i] = \min(dist[i], dist[j] + g[j][i])$$ 其中$j$为当前已确定最短路径的节点。
• 终止条件：所有有效节点被访问或$dist[1]$确定。

4. 复杂度优化

• 邻接矩阵：适用于$N \leq 100$的稠密图。
• 等级过滤：减少每次Dijkstra的节点数。

算法实现

代码框架

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

const int N = 105;
const int INF = 0x3f3f3f3f;
int g[N][N], dist[N], level[N], w[N];
bool vis[N];
int m, n;


int dijkstra(int minL, int maxL) {
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[0] = 0; 
    
    for (int i = 0; i <= n; i++) {
        int t = -1;
        for (int j = 0; j <= n; j++) {
            if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        
        if (t == -1 || dist[t] == INF) break;
        vis[t] = true;
        
        for (int j = 1; j <= n; j++) {
            if (level[j] >= minL && level[j] <= maxL) {
                if (dist[j] > dist[t] + g[t][j]) {
                    dist[j] = dist[t] + g[t][j];
                }
            }
        }
    }
    return dist[1];
}

int main() {
    cin >> m >> n;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i <= n; i++) {
        g[i][i] = 0;
    }
    
    for (int i = 1; i <= n; i++) {
        int p, l, x;
        cin >> p >> l >> x;
        w[i] = p;
        level[i] = l;
        g[0][i] = min(g[0][i], p);
        
        for (int j = 0; j < x; j++) {
            int t, v;
            cin >> t >> v;
            g[t][i] = min(g[t][i], v); 
        }
    }
    
    int ans = INF;
    for (int i = level[1] - m; i <= level[1]; i++) {
        ans = min(ans, dijkstra(i, i + m));
    }
    
    cout << ans << endl;
    return 0;
}

关键步骤

1. 输入处理：构建邻接矩阵$g$，初始化直接购买和替代交易的边权。
2. 等级区间枚举：遍历所有可能的$[L, L+M]$区间。
3. Dijkstra执行：对每个区间计算$dist[1]$，更新全局最小值$ans$。

复杂度分析

• 时间：$O(M \cdot N^2)$（共$M+1$次Dijkstra，每次$O(N^2)$）。
• 空间：$O(N^2)$（邻接矩阵存储）。