方法思路

1. 状态压缩动态规划：由于宝藏点数量较少（k ≤ 20），可以使用状态压缩（二进制位表示是否访问过某个宝藏点）。
2. Floyd算法预处理：计算所有宝藏点之间的最短路径，便于后续动态规划使用。
3. 动态规划状态转移：dp[state]表示访问state状态的所有宝藏点所需的最小体力，状态转移时考虑从已访问的点扩展到未访问的点。

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]); // 体力
        int m = Integer.parseInt(line[1]); // 金币
        int k = Integer.parseInt(line[2]); // 宝藏点数量
        int p = Integer.parseInt(line[3]); // 路径数量
        
        int[] value = new int[k]; // 宝藏价值
        int[] cost = new int[k];  // 所需金币
        
        for (int i = 0; i < k; i++) {
            line = br.readLine().split(" ");
            value[i] = Integer.parseInt(line[0]);
            cost[i] = Integer.parseInt(line[1]);
        }
        
        // 构建图
        int[][] graph = new int[k][k];
        for (int i = 0; i < k; i++) {
            Arrays.fill(graph[i], Integer.MAX_VALUE / 2); // 避免溢出
            graph[i][i] = 0;
        }
        
        for (int i = 0; i < p; i++) {
            line = br.readLine().split(" ");
            int u = Integer.parseInt(line[0]);
            int v = Integer.parseInt(line[1]);
            int t = Integer.parseInt(line[2]);
            graph[u][v] = Math.min(graph[u][v], t);
            graph[v][u] = Math.min(graph[v][u], t);
        }
        
        // Floyd算法计算最短路径
        for (int l = 0; l < k; l++) {
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][l] + graph[l][j]);
                }
            }
        }
        
        int maxValue = 0;
        int maxState = 1 << k;
        
        // 预计算每个状态的总金币和价值
        int[] stateCost = new int[maxState];
        int[] stateValue = new int[maxState];
        
        for (int state = 1; state < maxState; state++) {
            for (int i = 0; i < k; i++) {
                if ((state & (1 << i)) != 0) {
                    stateCost[state] += cost[i];
                    stateValue[state] += value[i];
                }
            }
        }
        
        // 动态规划数组：dp[state] = 收集状态state中所有宝藏所需的最小体力
        int[] dp = new int[maxState];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        
        // 初始状态：从每个点单独出发
        for (int i = 0; i < k; i++) {
            dp[1 << i] = 0;
        }
        
        // 状态转移
        for (int state = 1; state < maxState; state++) {
            // 如果当前状态金币超出，跳过
            if (stateCost[state] > m) continue;
            
            // 尝试从当前状态扩展到下一个状态
            for (int i = 0; i < k; i++) {
                if ((state & (1 << i)) != 0) { // i在当前状态中
                    for (int j = 0; j < k; j++) {
                        if ((state & (1 << j)) == 0) { // j不在当前状态中
                            int nextState = state | (1 << j);
                            // 如果从i到j的体力消耗加上当前状态的体力消耗小于下一状态的体力消耗
                            dp[nextState] = Math.min(dp[nextState], dp[state] + graph[i][j]);
                        }
                    }
                }
            }
        }
        
        // 检查每个状态是否可行并更新最大价值
        for (int state = 1; state < maxState; state++) {
            if (stateCost[state] <= m && dp[state] <= n) {
                maxValue = Math.max(maxValue, stateValue[state]);
            }
        }
        
        System.out.println(maxValue);
    }
}

Python

def main():
    n, m, k, p = map(int, input().split())  # 体力, 金币, 宝藏点数量, 路径数量
    
    value = []  # 宝藏价值
    cost = []   # 所需金币
    
    for _ in range(k):
        w, v = map(int, input().split())
        value.append(w)
        cost.append(v)
    
    # 构建图
    graph = [[float('inf')] * k for _ in range(k)]
    for i in range(k):
        graph[i][i] = 0
    
    for _ in range(p):
        u, v, t = map(int, input().split())
        graph[u][v] = min(graph[u][v], t)
        graph[v][u] = min(graph[v][u], t)
    
    # Floyd算法计算最短路径
    for l in range(k):
        for i in range(k):
            for j in range(k):
                if graph[i][l] != float('inf') and graph[l][j] != float('inf'):
                    graph[i][j] = min(graph[i][j], graph[i][l] + graph[l][j])
    
    max_value = 0
    
    # 枚举所有可能的宝藏组合
    for state in range(1, 1 << k):
        # 计算当前组合需要的金币总数
        total_cost = sum(cost[i] for i in range(k) if (state & (1 << i)))
        
        # 如果金币不够，跳过
        if total_cost > m:
            continue
        
        # 计算当前组合的总价值
        total_value = sum(value[i] for i in range(k) if (state & (1 << i)))
        
        # 检查是否能够收集这些宝藏
        can_collect = False
        
        # 对于每个可能的起点
        for start in range(k):
            if not (state & (1 << start)):
                continue
                
            # 使用TSP思想检查是否有足够的体力访问所有宝藏点
            remaining_points = state & ~(1 << start)
            if can_visit_all(graph, n, k, start, remaining_points):
                can_collect = True
                break
        
        if can_collect:
            max_value = max(max_value, total_value)
    
    print(max_value)

def can_visit_all(graph, energy, k, start, remaining):
    # 简单检查：如果只有起点，则可以访问
    if remaining == 0:
        return True
    
    # 贪心策略：每次选择最近的点
    current = start
    remaining_energy = energy
    
    while remaining:
        next_point = -1
        min_cost = float('inf')
        
        for i in range(k):
            if (remaining & (1 << i)) and graph[current][i] < min_cost and graph[current][i] <= remaining_energy:
                min_cost = graph[current][i]
                next_point = i
        
        if next_point == -1:
            return False
        
        remaining &= ~(1 << next_point)
        remaining_energy -= min_cost
        current = next_point
    
    return True

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

bool can_visit_all(vector<vector<int>>& graph, int energy, int k, int start, int remaining) {
    // 简单检查：如果只有起点，则可以访问
    if (remaining == 0) return true;
    
    // 贪心策略：每次选择最近的点
    int current = start;
    int remaining_energy = energy;
    
    while (remaining) {
        int next_point = -1;
        int min_cost = INT_MAX;
        
        for (int i = 0; i < k; i++) {
            if ((remaining & (1 << i)) && graph[current][i] < min_cost && graph[current][i] <= remaining_energy) {
                min_cost = graph[current][i];
                next_point = i;
            }
        }
        
        if (next_point == -1) return false;
        
        remaining &= ~(1 << next_point);
        remaining_energy -= min_cost;
        current = next_point;
    }
    
    return true;
}

int main() {
    int n, m, k, p;
    cin >> n >> m >> k >> p;  // 体力, 金币, 宝藏点数量, 路径数量
    
    vector<int> value(k);  // 宝藏价值
    vector<int> cost(k);   // 所需金币
    
    for (int i = 0; i < k; i++) {
        cin >> value[i] >> cost[i];
    }
    
    // 构建图
    vector<vector<int>> graph(k, vector<int>(k, INT_MAX));
    for (int i = 0; i < k; i++) {
        graph[i][i] = 0;
    }
    
    for (int i = 0; i < p; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        graph[u][v] = min(graph[u][v], t);
        graph[v][u] = min(graph[v][u], t);
    }
    
    // Floyd算法计算最短路径
    for (int l = 0; l < k; l++) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (graph[i][l] != INT_MAX && graph[l][j] != INT_MAX) {
                    graph[i][j] = min(graph[i][j], graph[i][l] + graph[l][j]);
                }
            }
        }
    }
    
    int max_value = 0;
    
    // 枚举所有可能的宝藏组合
    for (int state = 1; state < (1 << k); state++) {
        // 计算当前组合需要的金币总数
        int total_cost = 0;
        for (int i = 0; i < k; i++) {
            if (state & (1 << i)) {
                total_cost += cost[i];
            }
        }
        
        // 如果金币不够，跳过
        if (total_cost > m) continue;
        
        // 计算当前组合的总价值
        int total_value = 0;
        for (int i = 0; i < k; i++) {
            if (state & (1 << i)) {
                total_value += value[i];
            }
        }
        
        // 检查是否能够收集这些宝藏
        bool can_collect = false;
        
        // 对于每个可能的起点
        for (int start = 0; start < k; start++) {
            if (!(state & (1 << start))) continue;
            
            // 检查是否有足够的体力访问所有宝藏点
            int remaining_points = state & ~(1 << start);
            if (can_visit_all(graph, n, k, start, remaining_points)) {
                can_collect = true;
                break;
            }
        }
        
        if (can_collect) {
            max_value = max(max_value, total_value);
        }
    }
    
    cout << max_value << endl;
    
    return 0;
}