题解

题目描述

小明计划自驾旅行，起点为城市编号 0，终点为城市编号 N-1。他需要探访经过的每个城市，并支付相应的消费费用。由于他的汽车是电动车，充满电后最多只能行驶 M 公里，且中途城市没有充电桩，因此整个旅途的单次行驶距离不能超过 M 公里。每两个城市之间可能有道路连接，且行驶需要耗费一定的公里数。

需要设计一条行驶路线，使得在满足行驶距离不超过 M 公里的条件下，从起点到终点的探访费用最少。如果无法到达终点，输出 -1。

思路分析

本题是一个 带有资源（距离）限制的最小费用路径问题，需要在图上找到一条从起点到终点的路径，使得：

• 总行驶距离不超过 M 公里。
• 探访费用最少。

关键点：

• 边权重：每条边有一个行驶距离（耗电公里数）。
• 节点权重：每个节点有一个消费费用，需要累加。

需要设计一种算法，能够在满足总距离不超过 M 的前提下，找到最小的总费用。

算法选择

由于需要同时考虑 路径长度（距离） 和 累计费用，传统的最短路径算法如 Dijkstra 或 Bellman-Ford 无法直接应用。

适合本题的算法是 动态规划，具体为 状态扩展法，结合 队列优化（类似 SPFA）。

状态定义

使用一个二维数组 dp[node][distance]，表示：

• 到达节点 node，总行驶距离为 distance 时的最小累计费用。

状态转移

从当前状态 (node, distance) 出发，尝试通过所有相邻的边进行扩展：

• 对于每一条相邻的边 (node, next_node, edge_length)：
  • 计算新的总距离 new_distance = distance + edge_length。
  • 如果 new_distance <= M，则可以到达 next_node。
  • 更新 dp[next_node][new_distance]：
    • 如果 dp[node][distance] + fees[next_node] < dp[next_node][new_distance]，则更新。

初始条件

• dp[0][0] = fees[0]，表示从起点出发，费用为起点的费用，行驶距离为 0。

终止条件

• 最终，我们需要在所有到达终点的状态中，找出费用最小的一个。
• 遍历 dp[N-1][0...M]，取最小值。

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005; // 最大城市数量
const int MAXM = 1005; // 最大距离
const int INF = 1e9;   // 表示无穷大

struct Edge {
    int to;     // 目标城市编号
    int length; // 边的长度（耗电公里数）
};

int M, N, K;                // M：最大行驶距离，N：城市数量，K：边的数量
int fees[MAXN];             // 每个城市的消费费用
vector<Edge> graph[MAXN];   // 图的邻接表表示
int dp[MAXN][MAXM];         // 动态规划数组，dp[node][distance]表示到达node，距离为distance时的最小费用

int main() {
    // 读取最大行驶距离 M
    cin >> M;
    // 读取城市数量 N 和每个城市的消费费用
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> fees[i];
    }
    // 读取边的数量 K
    cin >> K;
    // 构建图的邻接表
    for (int i = 0; i < K; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        // 添加双向边
        graph[u].push_back({v, l});
        graph[v].push_back({u, l});
    }
    // 初始化 dp 数组，所有状态费用设为无穷大
    for (int i = 0; i < N; i++) {
        fill(dp[i], dp[i] + M + 1, INF);
    }
    dp[0][0] = fees[0]; // 起点状态，费用为起点费用，距离为0

    // 队列用于优化搜索过程，存储状态 (城市编号，累计距离)
    queue<pair<int, int>> q;
    q.push({0, 0});
    bool inQueue[MAXN][MAXM]; // 标记某个状态是否在队列中，避免重复入队
    memset(inQueue, false, sizeof(inQueue));
    inQueue[0][0] = true;

    // 开始状态扩展（类似SPFA算法）
    while (!q.empty()) {
        int u = q.front().first;    // 当前城市编号
        int dist = q.front().second; // 当前累计行驶距离
        q.pop();
        inQueue[u][dist] = false;    // 状态出队，标记为不在队列中

        // 遍历当前城市的所有邻接边
        for (auto &edge : graph[u]) {
            int v = edge.to;            // 相邻城市编号
            int length = edge.length;   // 从 u 到 v 的距离
            int newDist = dist + length; // 新的累计距离

            // 如果新的累计距离不超过最大行驶距离 M
            if (newDist <= M) {
                // 如果通过当前路径可以达到更小的费用
                if (dp[u][dist] + fees[v] < dp[v][newDist]) {
                    dp[v][newDist] = dp[u][dist] + fees[v]; // 更新最小费用
                    // 如果新的状态不在队列中，则将其加入队列
                    if (!inQueue[v][newDist]) {
                        q.push({v, newDist});
                        inQueue[v][newDist] = true;
                    }
                }
            }
        }
    }

    // 在所有可能的累计距离下，找到到达终点的最小费用
    int result = INF;
    for (int d = 0; d <= M; d++) {
        result = min(result, dp[N - 1][d]);
    }

    // 输出结果
    if (result == INF) {
        cout << -1 << endl; // 无法到达终点
    } else {
        cout << result << endl; // 输出最小费用
    }
    return 0;
}

python

from collections import deque

MAXN = 1005  # 最大城市数量
MAXM = 1005  # 最大距离
INF = int(1e9)  # 表示无穷大

# 读取最大行驶距离 M
M = int(input())
data = input().split()
N = int(data[0])             # 城市数量 N
fees = list(map(int, data[1:]))  # 每个城市的消费费用
K = int(input())             # 边的数量 K
graph = [[] for _ in range(N)]   # 图的邻接表表示

# 构建图的邻接表
for _ in range(K):
    u, v, l = map(int, input().split())
    graph[u].append((v, l))  # 添加边 u -> v
    graph[v].append((u, l))  # 添加边 v -> u（双向边）

# 初始化 dp 数组，dp[node][distance] 表示到达 node，距离为 distance 时的最小费用
dp = [[INF] * (M + 1) for _ in range(N)]
dp[0][0] = fees[0]  # 起点状态，费用为起点费用，距离为0

# 队列用于优化搜索过程，存储状态 (城市编号，累计距离)
q = deque()
q.append((0, 0))
in_queue = [[False] * (M + 1) for _ in range(N)]  # 标记状态是否在队列中
in_queue[0][0] = True

# 开始状态扩展
while q:
    u, dist = q.popleft()
    in_queue[u][dist] = False  # 状态出队

    # 遍历当前城市的所有邻接边
    for v, length in graph[u]:
        new_dist = dist + length  # 新的累计距离

        # 如果新的累计距离不超过最大行驶距离 M
        if new_dist <= M:
            # 如果通过当前路径可以达到更小的费用
            if dp[u][dist] + fees[v] < dp[v][new_dist]:
                dp[v][new_dist] = dp[u][dist] + fees[v]  # 更新最小费用
                # 如果新的状态不在队列中，则将其加入队列
                if not in_queue[v][new_dist]:
                    q.append((v, new_dist))
                    in_queue[v][new_dist] = True

# 在所有可能的累计距离下，找到到达终点的最小费用
result = min(dp[N - 1][:M + 1])

# 输出结果
if result == INF:
    print(-1)  # 无法到达终点
else:
    print(result)  # 输出最小费用

java

import java.util.*;

public class Main {
    static final int MAXN = 1005; // 最大城市数量
    static final int MAXM = 1005; // 最大距离
    static final int INF = Integer.MAX_VALUE;

    // 边的类，表示从当前城市到目标城市的距离
    static class Edge {
        int to;     // 目标城市编号
        int length; // 边的长度（耗电公里数）

        Edge(int to, int length) {
            this.to = to;
            this.length = length;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt(); // 最大行驶距离 M
        int N = sc.nextInt(); // 城市数量 N
        int[] fees = new int[N]; // 每个城市的消费费用
        for (int i = 0; i < N; i++) {
            fees[i] = sc.nextInt();
        }
        int K = sc.nextInt(); // 边的数量 K
        List<Edge>[] graph = new ArrayList[N]; // 图的邻接表表示
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }
        // 构建图的邻接表
        for (int i = 0; i < K; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int l = sc.nextInt();
            graph[u].add(new Edge(v, l)); // 添加边 u -> v
            graph[v].add(new Edge(u, l)); // 添加边 v -> u（双向边）
        }
        // 初始化 dp 数组，dp[node][distance] 表示到达 node，距离为 distance 时的最小费用
        int[][] dp = new int[N][M + 1];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], INF); // 所有状态费用设为无穷大
        }
        dp[0][0] = fees[0]; // 起点状态，费用为起点费用，距离为0

        // 队列用于优化搜索过程，存储状态 [城市编号，累计距离]
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        boolean[][] inQueue = new boolean[N][M + 1]; // 标记状态是否在队列中
        inQueue[0][0] = true;

        // 开始状态扩展
        while (!q.isEmpty()) {
            int[] current = q.poll();
            int u = current[0];     // 当前城市编号
            int dist = current[1];  // 当前累计行驶距离
            inQueue[u][dist] = false; // 状态出队

            // 遍历当前城市的所有邻接边
            for (Edge edge : graph[u]) {
                int v = edge.to;           // 相邻城市编号
                int length = edge.length;  // 从 u 到 v 的距离
                int newDist = dist + length; // 新的累计距离

                // 如果新的累计距离不超过最大行驶距离 M
                if (newDist <= M) {
                    // 如果通过当前路径可以达到更小的费用
                    if (dp[u][dist] + fees[v] < dp[v][newDist]) {
                        dp[v][newDist] = dp[u][dist] + fees[v]; // 更新最小费用
                        // 如果新的状态不在队列中，则将其加入队列
                        if (!inQueue[v][newDist]) {
                            q.offer(new int[]{v, newDist});
                            inQueue[v][newDist] = true;
                        }
                    }
                }
            }
        }
        // 在所有可能的累计距离下，找到到达终点的最小费用
        int result = INF;
        for (int d = 0; d <= M; d++) {
            result = Math.min(result, dp[N - 1][d]);
        }
        // 输出结果
        if (result == INF) {
            System.out.println(-1); // 无法到达终点
        } else {
            System.out.println(result); // 输出最小费用
        }
        sc.close();
    }
}

题目内容

随着疫情放开，小明准备自驾旅行，旅行中经过的每个城市都有一些朋友需要去探访消费，最近小明有点经济紧张，请帮小明设计一下行驶路线，能用最少的探访费用到达终点。

1、小明的汽车是电车，最多只能行驶$M$公里，且中间城市没有充电桩

2、假如旅行一共有$N$个城市，城市序号分别为$0,1,2，。。。，N-1$，则起点为$0$，终点为$N-1$

3、每个城市游玩需要费用为$fees = [f0,f1,f2,f3...]$，每项费用$f>=0$，总费用包括$fees[0]$和$fees[N-1]$

4、每两个城市之间耗电通过{$i,j,k$}标识从i到j或者从$j$到$i$是可以相互到达的，并且需要耗电$k$公里，未定义的视为不可到达

输入描述

第一行:汽车最大可行驶距离$M(0<M<=1000)$

第二行:城市数量$N(1<N<=1000)$，及每个城市的消费费用

第三行:城市间联通关系数量$K$

后续$K$行:$i\ j\ k$表示到或者$j$到$i$需要耗电$k$公里

输出描述

可达:输出最少的探访费用

不可达:输出$-1$

样例1

输入

500
4 1000 3000 4000 2000
5
0 1 200
0 3 250
1 3 300
0 2 150 
2 3 250

输出

3000

说明

最优路径为$0->3$，总共需要耗电$250$公里，需要支付费用$3000$

样例2

输入

400
4 1000 3000 4000 2000
4 
0 1 200
1 3 300
0 2 150
2 3 250

输出

7000