(新卷,200分)- 快递员的烦恼（Java JS Python C）

(新卷,200分)- 快递员的烦恼（Java & JS & Python & C）

题目描述

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

注意：

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

输入描述

首行输入两个正整数n、m

接下来 n 行，输入快递公司发布的客户快递信息，格式为：

客户id 投递站到客户之间的距离distance

再接下俩的 m 行，是快递员自行查找的客户与客户之间的距离信息，格式为

客户id1 客户id2 distance

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

规格：

• 0 < n ≤ 10
• 0 ≤ m ≤ 10
• 0 < 客户id ≤ 1000
• 0 < distance ≤ 10000

输出描述

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

用例

题目解析

下图中 0节点 代表快递站。

用例1图示

用例2图示

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { const [n, m] = (await readline()).split(" ").map(Number); // floyd算法需要基于dist和path矩阵求解 // dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵, 对与不直连的两点，距离为无穷大 const dist = new Array(n + 1) .fill(0) .map(() => new Array(n + 1).fill(Infinity)); // path[i][j] 用于记录点 i->j 最短距离情况下需要经过的中转点，初始时默认任意两点间无中转点，即默认path[i][j] = -1 const path = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(-1)); // 由于本题的客户id不是顺序的，因此这里需要将客户id离散化处理 const map = {}; for (let i = 1; i <= n; i++) { const [id, dis] = (await readline()).split(" ").map(Number); // 离散化处理 map[id] = i; // 投递站到客户之间的距离distance dist[0][i] = dis; dist[i][0] = dis; } for (let i = 1; i <= m; i++) { const [id1, id2, dis] = (await readline()).split(" ").map(Number); const i1 = map[id1]; const i2 = map[id2]; // 客户与客户之间的距离信息 dist[i1][i2] = dis; dist[i2][i1] = dis; } // floyd算法调用 floyd(); // ans记录经过所有点后回到出发点的最短距离 let ans = Infinity; // 全排列模拟经过所有点的路径 dfs(0, 0, new Array(n + 1).fill(false), 0); console.log(ans); // floyd算法求解图中任意两点之间的最短路径 function floyd() { for (let k = 0; k < n + 1; k++) { for (let i = 0; i < n + 1; i++) { for (let j = 0; j < n + 1; j++) { // newDist是经过k后，i->j的距离 const newDist = dist[i][k] + dist[k][j]; // 如果newDist是i->j的更短路径 if (newDist < dist[i][j]) { // 则更新i->j的最短距离 dist[i][j] = newDist; // 且此更短距离需要经过k, path[i][j]即记录 i->j 最短距离下需要经过点 k path[i][j] = k; } } } } } /** * 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同 // * 求某个全排列过程中，可以通过dist数组，累计上一个点i到下一个点j的最短路径dist[i][j] * * @param pre 上一个点, 初始为0，表示从快递站出发 * @param sum 当前全排列路径累计的路径权重 * @param used 全排列used数组，用于标记哪些点已使用过 * @param level 用于记录排列的长度 */ function dfs(pre, sum, used, level) { if (level == n) { // 此时pre是最后一个客户所在点，送完最后一个客户后，快递员需要回到快递站，因此最终累计路径权重为 sum + dist[pre][0] // 我们保留最小权重路径 ans = Math.min(ans, sum + dist[pre][0]); return; } for (let i = 1; i <= n; i++) { if (used[i]) continue; used[i] = true; dfs(i, sum + dist[pre][i], used, level + 1); used[i] = false; } } })();

Java算法源码

import java.util.HashMap; import java.util.Scanner; public class Main { static int n; static int[][] dist; static int[][] path; static int ans; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); int m = sc.nextInt(); // floyd算法需要基于dist和path矩阵求解 // dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵 dist = new int[n + 1][n + 1]; // path[i][j] 用于记录点 i->j 最短距离情况下需要经过的中转点，初始时默认任意两点间无中转点，即默认path[i][j] = -1 path = new int[n + 1][n + 1]; 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] = Integer.MAX_VALUE; } path[i][j] = -1; } } // 由于本题的客户id不是顺序的，因此这里需要将客户id离散化处理 HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 1; i <= n; i++) { int id = sc.nextInt(); int dis = sc.nextInt(); // 离散化处理 map.put(id, i); // 投递站到客户之间的距离distance dist[0][i] = dis; dist[i][0] = dis; } for (int i = 1; i <= m; i++) { int id1 = sc.nextInt(); int id2 = sc.nextInt(); int dis = sc.nextInt(); int i1 = map.get(id1); int i2 = map.get(id2); // 客户与客户之间的距离信息 dist[i1][i2] = dis; dist[i2][i1] = dis; } // floyd算法调用 floyd(); // ans记录经过所有点后回到出发点的最短距离 ans = Integer.MAX_VALUE; // 全排列模拟经过所有点的路径 dfs(0, 0, new boolean[n + 1], 0); System.out.println(ans); } // floyd算法求解图中任意两点之间的最短路径 public static 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; // 且此更短距离需要经过k, path[i][j]即记录 i->j 最短距离下需要经过点 k path[i][j] = k; } } } } } /** * 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同 // * 求某个全排列过程中，可以通过dist数组，累计上一个点i到下一个点j的最短路径dist[i][j] * * @param pre 上一个点, 初始为0，表示从快递站出发 * @param sum 当前全排列路径累计的路径权重 * @param used 全排列used数组，用于标记哪些点已使用过 * @param level 用于记录排列的长度 */ public static void dfs(int pre, int sum, boolean[] used, int level) { if (level == n) { // 此时pre是最后一个客户所在点，送完最后一个客户后，快递员需要回到快递站，因此最终累计路径权重为 sum + dist[pre][0] // 我们保留最小权重路径 ans = Math.min(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], used, level + 1); used[i] = false; } } }

Python算法源码

import sys # 输入获取 n, m = map(int, input().split()) # floyd算法需要基于dist和path矩阵求解 # dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵 dist = [[sys.maxsize] * (n + 1) for _ in range(n + 1)] # path[i][j] 用于记录点 i->j 最短距离情况下需要经过的中转点，初始时默认任意两点间无中转点，即默认path[i][j] = -1 path = [[-1] * (n + 1) for _ in range(n + 1)] # 由于本题的客户id不是顺序的，因此这里需要将客户id离散化处理 dic = {} for i in range(1, n + 1): idx, dis = map(int, input().split()) # 离散化处理 dic[idx] = i # 投递站到客户之间的距离distance dist[0][i] = dis dist[i][0] = dis for i in range(1, m + 1): idx1, idx2, dis = map(int, input().split()) i1 = dic[idx1] i2 = dic[idx2] # 客户与客户之间的距离信息 dist[i1][i2] = dis dist[i2][i1] = dis # ans记录经过所有点后回到出发点的最短距离 ans = sys.maxsize # floyd算法求解图中任意两点之间的最短路径 def floyd(): for k in range(n + 1): for i in range(n + 1): for j in range(n + 1): # newDist是经过k后，i->j的距离 newDist = dist[i][k] + dist[k][j] # 如果newDist是i->j的更短路径 if newDist < dist[i][j]: # 则更新i->j的最短距离 dist[i][j] = newDist # 且此更短距离需要经过k, path[i][j]即记录 i->j 最短距离下需要经过点 k path[i][j] = k def dfs(pre, sumDis, used, level): """ 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同 // 求某个全排列过程中，可以通过dist数组，累计上一个点i到下一个点j的最短路径dist[i][j] :param pre: 上一个点, 初始为0，表示从披萨店出发 :param sumDis: 当前全排列路径累计的路径权重 :param used: 全排列used数组，用于标记哪些点已使用过 :param level: 用于记录排列的长度 """ global ans if level == n: # 此时pre是最后一个客户所在点，送完最后一个客户后，司机需要回到披萨店，因此最终累计路径权重为 sum + dist[pre][0] # 我们保留最小权重路径 ans = min(ans, sumDis + dist[pre][0]) return for i in range(1, n + 1): if used[i]: continue used[i] = True dfs(i, sumDis + dist[pre][i], used, level + 1) used[i] = False # 算法入口 def main(): # floyd算法调用 floyd() # 全排列模拟经过所有点的路径 dfs(0, 0, [False] * (n + 1), 0) print(ans) # 算法调用 main()

C算法源码

#include <stdio.h> #include <limits.h> #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define MAX_SIZE 11 #define MAX_ID 1000 int n; int dist[MAX_SIZE][MAX_SIZE]; int path[MAX_SIZE][MAX_SIZE]; int ans; /** * 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同 // * 求某个全排列过程中，可以通过dist数组，累计上一个点i到下一个点j的最短路径dist[i][j] * * @param pre 上一个点, 初始为0，表示从披萨店出发 * @param sum 当前全排列路径累计的路径权重 * @param used 全排列used数组，用于标记哪些点已使用过 * @param level 用于记录排列的长度 */ void dfs(int pre, int sum, int used[], int level) { if (level == n) { // 此时pre是最后一个客户所在点，送完最后一个客户后，司机需要回到披萨店，因此最终累计路径权重为 sum + dist[pre][0] // 我们保留最小权重路径 ans = MIN(ans, sum + dist[pre][0]); return; } for (int i = 1; i <= n; i++) { if (used[i]) continue; used[i] = 1; dfs(i, sum + dist[pre][i], used, level + 1); used[i] = 0; } } // 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; // 且此更短距离需要经过k, path[i][j]即记录 i->j 最短距离下需要经过点 k path[i][j] = k; } } } } } 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; } path[i][j] = -1; } } // 由于本题的客户id不是顺序的，因此这里需要将客户id离散化处理 int map[MAX_ID]; 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(); // ans记录经过所有点后回到出发点的最短距离 ans = INT_MAX; // 全排列模拟经过所有点的路径 int used[MAX_SIZE] = {0}; dfs(0, 0, used, 0); printf("%d\n", ans); }