太原自学网站建设佛山网页设计培训

太原自学网站建设,佛山网页设计培训,已有网站域名 怎么做网站,深圳龙岗区律师(新卷,200分)- 快递员的烦恼#xff08;Java JS Python C#xff09;题目描述快递公司每日早晨#xff0c;给每位快递员推送需要送到客户手中的快递以及路线信息#xff0c;快递员自己又查找了一些客户与客户之间的路线距离信息#xff0c;请你依据这些…(新卷,200分)- 快递员的烦恼Java JS Python C题目描述快递公司每日早晨给每位快递员推送需要送到客户手中的快递以及路线信息快递员自己又查找了一些客户与客户之间的路线距离信息请你依据这些信息给快递员设计一条最短路径告诉他最短路径的距离。注意不限制快递包裹送到客户手中的顺序但必须保证都送到客户手中用例保证一定存在投递站到每位客户之间的路线但不保证客户与客户之间有路线客户位置及投递站均允许多次经过所有快递送完后快递员需回到投递站输入描述首行输入两个正整数n、m接下来 n 行输入快递公司发布的客户快递信息格式为客户id 投递站到客户之间的距离distance再接下俩的 m 行是快递员自行查找的客户与客户之间的距离信息格式为客户id1 客户id2 distance在每行数据中数据与数据之间均以单个空格分隔规格0 n ≤ 100 ≤ m ≤ 100 客户id ≤ 10000 distance ≤ 10000输出描述最短路径距离如无法找到请输出-1用例输入2 11 10002 12001 2 300输出2500说明路径1快递员先把快递送到客户1中接下来直接走客户1到客户2之间的直通路线最后走投递站和客户2之间的路回到投递站距离为 1000 300 1200 2500路径2快递员先把快递送到客户1手中接下来回到快递站再出发把客户2的快递送过去再回到快递站距离为 1000 1000 1200 1200 4400路径3快递员先把快递送到客户2手中接下来直接走客户2到客户1之间的直通线路最后走投递站和客户1之间的路回到投递站距离为 1200 300 1000 2500其他路径......所有路径中最短路径距离为 2500输入5 15 10009 120017 300132 700500 23005 9 400输出9200说明在所有可行的路径中最短路径长度为 1000 400 1200 300 300 700 700 2300 2300 9200题目解析下图中 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离散化处理 HashMapInteger, 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); }