返回目录

题目描述

快递公司每日早晨，给每位快递员推送需要送到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最例短路径， 告诉他最短路径的距离。

注意：

1. 不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中
2. 用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过。
3. 所有快递送完后，快递员需回到投递站

输入描述

首行输入两个正整数n,m。

接下面n行，输入快递公司发布的客户快递信息，
格式为：客户id 投递站到客户之间的距离distance

再接下来的m行，是快递员自行查找的客户与客户之间的距离信息，
格式为：客户1id 客户2id distance

在每行数据中，数据与数据之间均以单个空格分割

规格;
0 < n <=10
0 <= m <= 10
0< 客户id <= 1000
0< distance <= 10000

输出描述

最短路径距离，如无法找到，请输出 -1

示例：

解题思路

• 读取每个客户的ID和该客户到配送站的距离，更新距离矩阵和映射字典。
• 读取额外路线信息，更新距离矩阵中客户之间的距离。
• 创建一个动态规划数组，用于记录到达每个状态（客户的访问情况）的最短距离。
• 初始化一个队列，用于执行广度优先搜索（BFS）。

1. 广度优先搜索和动态规划：

   • 从配送站开始，对每个可能的客户位置进行搜索。
   • 对于当前位置，遍历所有其他客户位置，检查是否存在一条到达下一个客户的路线。
   • 计算到达下一个客户的新状态，如果该状态未被访问过或者可以通过更短的距离到达，则更新动态规划数组。
   • 将新状态加入队列，以便继续搜索。

2. 搜索结束条件：

   • 当队列为空时，搜索结束。

3. 输出结果：

   • 从动态规划数组中获取访问所有客户并返回配送站的最短距离。
   • 如果最短距离不是无穷大，则存在有效路径，输出最短距离；否则输出-1表示无法访问所有客户。

模拟计算过程

对于给定的用例，我们有2个客户和1条额外的路线。下面是模拟计算过程的详细步骤：

1. 初始化变量：

   • 客户数量 n = 2，额外路线数量 m = 1。
   • 无穷大值 inf 用于初始化距离。
   • 距离矩阵 dis 初始化为 [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]。
   • 映射字典 mapping 初始化为空。

2. 构建距离矩阵和映射字典：

   • 客户1的ID为1，到配送站的距离为1000，更新 dis 和 mapping：dis[0][1] = dis[1][0] = 1000，mapping[1] = 1。
   • 客户2的ID为2，到配送站的距离为1200，更新 dis 和 mapping：dis[0][2] = dis[2][0] = 1200，mapping[2] = 2。
   • 额外路线连接客户1和客户2，距离为300，更新 dis：dis[1][2] = dis[2][1] = 300。

3. 初始化动态规划数组和队列：

   • 动态规划数组 f 初始化为 [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]。
   • 队列 q 初始化为 [(0, 0, 0)]。

4. 广度优先搜索：

   • 从队列中取出 (0, 0, 0)，表示当前没有访问任何客户，位置在配送站，当前距离为0。
   • 尝试访问客户1，状态更新为 1 << (1 - 1) = 1，距离更新为 0 + 1000 = 1000，将 (1, 1, 1000) 加入队列。
   • 尝试访问客户2，状态更新为 1 << (2 - 1) = 2，距离更新为 0 + 1200 = 1200，将 (2, 2, 1200) 加入队列。
   • 队列现在为 [(1, 1, 1000), (2, 2, 1200)]。

5. 继续广度优先搜索：

   • 取出 (1, 1, 1000)，尝试访问客户2，状态更新为 1 | (1 << (2 - 1)) = 3，距离更新为 1000 + 300 = 1300，将 (3, 2, 1300) 加入队列。
   • 取出 (2, 2, 1200)，尝试访问客户1，状态更新为 2 | (1 << (1 - 1)) = 3，距离更新为 1200 + 300 = 1500，但由于状态 3 已经以更短的距离 1300 被访问过，所以不更新。

6. 输出结果：

   • 最终状态为 3，表示所有客户都被访问过，返回配送站的距离为 f[3][0]。
   • 由于我们没有直接从客户返回配送站的距离，我们需要考虑从最后一个客户返回配送站的距离。
   • 最短路径为从配送站到客户1，然后到客户2，再返回配送站，距离为 1000 + 300 + 1200 = 2500。
   • 输出最短距离 2500。

Python算法源码

from collections import deque

# 读取客户数量和路线数量
n, r = map(int, input().split())

# 定义无穷大用于初始化距离矩阵
inf = float('inf')

# 初始化距离矩阵，所有值设为无穷大
d = [[inf] * (n + 1) for _ in range(n + 1)]

# 创建映射字典，将客户ID映射到矩阵索引
m = {}

# 读取客户信息，填充距离矩阵和映射字典
for i in range(n):
    id, dist = map(int, input().split())
    m[id] = i + 1
    d[0][i + 1] = d[i + 1][0] = dist

# 读取额外的路线信息，更新距离矩阵
for _ in range(r):
    id1, id2, dist = map(int, input().split())
    i1 = m[id1]
    i2 = m[id2]
    d[i1][i2] = d[i2][i1] = dist

# 初始化动态规划数组，用于记录到达每个状态的最短距离
dp = [[inf] * (n + 1) for _ in range(1 << n)]

# 初始化队列，用于广度优先搜索
q = deque()
q.append((0, 0, 0))  # 将起始状态加入队列

# 设置起始点到起始点的距离为0
dp[0][0] = 0

# 执行广度优先搜索
while q:
    cs, cp, _ = q.popleft()
    cd = dp[cs][cp]  # 当前状态的最短距离
    for np in range(n + 1):  # 遍历所有可能的下一个位置
        if np != cp and d[cp][np] != inf:  # 如果下一个位置不是当前位置且可达
            ns = cs | (1 << (np - 1)) if np != 0 else cs  # 计算新状态
            if dp[ns][np] > cd + d[cp][np]:  # 如果新状态的距离可以被更新
                dp[ns][np] = cd + d[cp][np]  # 更新距离
                q.append((ns, np, 0))  # 将新状态加入队列

# 获取访问所有客户并返回配送站的最短距离
min_d = dp[(1 << n) - 1][0]

# 打印最短距离或-1（如果不存在有效路径）
print(min_d if min_d != inf else -1)

C算法源码

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define MAX_N 12

int n;
int dist[MAX_N][MAX_N] = {0}; // dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵
int ans = INT_MAX; // ans记录经过所有点后回到出发点的最短距离
bool used[MAX_N] = {false};

// floyd算法求解图中任意两点之间的最短路径
void floyd() {
    for (int k = 0; k < n + 1; k++) {
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                // newDist是经过k后，i->j的距离
                int newDist = dist[i][k] + dist[k][j];

                // 如果newDist是i->j的更短路径
                if (newDist < dist[i][j]) {
                    // 则更新i->j的最短距离
                    dist[i][j] = newDist;
                }
            }
        }
    }
}

/*!
 * 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同
 * 求某个全排列过程中，可以通过dist数组，累计上一个点i到下一个点j的最短路径dist[i][j]
 * @param pre 上一个点, 初始为0，表示从快递站出发
 * @param sum 当前全排列路径累计的路径权重
 * @param level 用于记录排列的长度
 */
void dfs(int pre, int sum, int level) {
    if (level == n) {
        // 此时pre是最后一个客户所在点，送完最后一个客户后，快递员需要回到快递站，因此最终累计路径权重为 sum + dist[pre][0]
        // 我们保留最小权重路径
        ans = ans < (sum + dist[pre][0]) ? ans : (sum + dist[pre][0]);
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;

        used[i] = true;
        dfs(i, sum + dist[pre][i], level + 1);
        used[i] = false;
    }
}

int main() {
    int m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < n + 1; j++) {
            // 初始时默认i,j不相连，即i,j之间距离无穷大
            if (i != j) {
                dist[i][j] = INT_MAX;
            }
        }
    }

    // 由于本题的客户id不是顺序的，因此这里需要将客户id离散化处理
    int map[MAX_N + 1] = {0};

    for (int i = 1; i <= n; i++) {
        int id, dis;
        scanf("%d %d", &id, &dis);

        // 离散化处理
        map[id] = i;

        // 投递站到客户之间的距离distance
        dist[0][i] = dis;
        dist[i][0] = dis;
    }

    for (int i = 1; i <= m; i++) {
        int id1, id2, dis;
        scanf("%d %d %d", &id1, &id2, &dis);

        int i1 = map[id1];
        int i2 = map[id2];

        // 客户与客户之间的距离信息
        dist[i1][i2] = dis;
        dist[i2][i1] = dis;
    }

    // floyd算法调用
    floyd();
    // 全排列模拟经过所有点的路径
    dfs(0, 0, 0);

    printf("%d\n", ans);

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    static final int MAX_N = 12;
    static int n;
    static int[][] dist = new int[MAX_N + 1][MAX_N + 1];
    static int[][] dp = new int[1 << MAX_N][MAX_N + 1];
    static Map<Integer, Integer> map = new HashMap<>();

    static void main() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 读取客户数量
        int r = scanner.nextInt(); // 读取路线数量

        final int inf = Integer.MAX_VALUE; // 定义无穷大值

        // 初始化距离矩阵，所有值设置为无穷大
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dist[i], inf);
        }

        // 读取客户信息，填充距离矩阵和映射字典
        for (int i = 1; i <= n; i++) {
            int id = scanner.nextInt();
            int distance = scanner.nextInt();
            map.put(id, i);
            dist[0][i] = dist[i][0] = distance;
        }

        // 读取额外的路线信息，更新距离矩阵
        for (int i = n + 1; i <= n + r; i++) {
            int id1 = scanner.nextInt();
            int id2 = scanner.nextInt();
            int distance = scanner.nextInt();
            int i1 = map.get(id1);
            int i2 = map.get(id2);
            dist[i1][i2] = dist[i2][i1] = distance;
        }

        // 初始化动态规划数组，用于记录到达每个状态的最短距离
        for (int[] row : dp) {
            Arrays.fill(row, inf);
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        dp[0][0] = 0;

        // 执行广度优先搜索
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cs = current[0]; // 当前状态
            int cp = current[1]; // 当前位置
            int cd = dp[cs][cp]; // 当前距离
            for (int np = 0; np <= n; np++) {
                if (np != cp && dist[cp][np] != inf) {
                    int ns = np != 0 ? cs | (1 << (np - 1)) : cs; // 更新状态
                    if (dp[ns][np] > cd + dist[cp][np]) {
                        dp[ns][np] = cd + dist[cp][np]; // 更新最短距离
                        queue.offer(new int[]{ns, np});
                    }
                }
            }
        }

        int minD = dp[(1 << n) - 1][0]; // 获取访问所有客户并返回配送站的最短距离
        System.out.println(minD != inf ? minD : -1); // 打印最短距离或-1（如果不存在有效路径）
    }

    public static void main(String[] args) {
        main();
    }
}