庆阳网站设计费用,wordpress导出表,淮北刚刚发生的事,wordpress如何实时刷新数据库OD统一考试#xff08;C卷#xff09; 分值#xff1a; 200分 题解#xff1a; Java / Python / C 题目描述
快递公司每日早晨#xff0c;给每位快递员推送需要淡到客户手中的快递以及路线信息#xff0c;快递员自己又查找了一些客户与客户之间的路线距离信息#xff0… OD统一考试C卷 分值 200分 题解 Java / Python / C 题目描述
快递公司每日早晨给每位快递员推送需要淡到客户手中的快递以及路线信息快递员自己又查找了一些客户与客户之间的路线距离信息请你依据这些信息给快递员设计一条最短路径告诉他最短路径的距离。 不限制快递包裹送到客户手中的顺序但必须保证都送到客户手中 用例保证一定存在投递站到每位客户之间的路线但不保证客户与客户之间有路线客户位置及投递站均允许多次经过 所有快递送完后快递员需回到投递站
输入描述
首行输入两个正整数n、m.
接下来n行输入快递公司发布的客户快递信息格式为客户id 投递站到客户之间的距离distance
再接下来的m行是快递员自行查找的客户与客户之间的距离信息格式为客户1id 客户2id distance
在每行数据中数据与数据之间均以单个空格分割规格: 0 n 10 0 m 10 0 客户id 1000 0 distance 10000 输出描述
最短路径距离如无法找到请输出-1
示例1
输入
2 1
1 1000
2 1200
1 2 300输出
2500说明
快递员先把快递送到客户1手中接下来直接走客户1到客户2之间的直通线路最后走投递站和客户2之间的路回到投递站距离为10003001200 2500示例2
输入
5 1
5 1000
9 1200
17 300
132 700
500 2300
5 9 400输出
9200题解 这道题目属于图论中的最短路径问题。题目要求找到一条路径使得快递员从投递站出发依次经过所有客户最后回到投递站使得路径的总距离最短。 首先我们需要构建一个图图中的节点表示投递站和所有客户边表示它们之间的距离。由于题目中给出了客户之间的距离信息我们可以使用 Floyd 算法来计算任意两点之间的最短距离。 接下来我们使用动态规划来求解最短路径。定义dp[state][last]表示当前情况下已经投递的客户集合为state上一次投递的客户为last时已经走过的最短距离。状态转移方程为 dp[state | (1 last)][last] min(dp[state | (1 last)][last], dp[state][i] dist[i][last])其中state为二进制表示的已经投递的客户集合state | (1 last)表示将state中last位置设置为1last 表示上一次投递的状态。dist[i][last]表示投递的客户的最短距离。 时间复杂度 Floyd-Warshall算法的时间复杂度为O(n3)动态规划的时间复杂度为O(2n * n2)总体时间复杂度为O(n3 2^n * n^2)。 空间复杂度 空间复杂度主要由存储距离矩阵和动态规划数组决定为O(n^2 2^n * n)。 Java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/*** author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt(), m scanner.nextInt();int[][] dist new int[n 1][n 1];for (int i 0; i dist.length; i) Arrays.fill(dist[i], Integer.MAX_VALUE);// 客户id 和索引下标的对照表MapInteger, Integer idxMap new HashMap();// 初始化客户id 到 投递站(0) 之间的距离for (int idx 1; idx n; idx) {int cid scanner.nextInt();int distance scanner.nextInt();dist[0][idx] dist[idx][0] distance;idxMap.put(cid, idx);}// 初始化客户与客户之间的距离for (int i 0; i m; i) {int cid1 scanner.nextInt(), cid2 scanner.nextInt(), distance scanner.nextInt();int idx1 idxMap.get(cid1), idx2 idxMap.get(cid2);dist[idx1][idx2] dist[idx2][idx1] distance;}// Floyd-Warshall算法 求出所有点之间的最短距离 时间复杂度为O(n^3)for (int k 0; k n; k) {dist[k][k] 0; // 自己到自己的距离为0for (int i 0; i n; i) {for (int j 0; j n; j) {dist[i][j] Math.min(dist[i][j], dist[i][k] dist[k][j]);}}}// dp[state][last] 当前情况走过的最短距离// state 表示已经投递的客户 指定二进制位为1表示已经投递last表示上一次投递的客户int[][] dp new int[1 (n 1)][n 1];for (int i 0; i (1 (n 1)); i) Arrays.fill(dp[i], Integer.MAX_VALUE);dp[1][0] 0; // 初始状态在投递站for (int state 0; state (1 (n 1)); state) {for (int i 0; i n; i) {if ((state i 1) 1 dp[state][i] ! Integer.MAX_VALUE) { // 如果 i 已经投递 且 可达for (int last 0; last n; last) {dp[state | (1 last)][last] Math.min(dp[state | (1 last)][last], dp[state][i] dist[i][last]);}}}}System.out.println(dp[(1 (n 1)) - 1][0]);}
}Python
from math import infn, m map(int, input().split())
dist [[inf] * (n 1) for _ in range(n 1)]# 客户id 和索引下标的对照表
idx_map {}# 初始化客户id 到 投递站(0) 之间的距离
for idx in range(1, n 1):cid, distance map(int, input().split())dist[0][idx] dist[idx][0] distanceidx_map[cid] idx# 初始化客户与客户之间的距离
for _ in range(m):cid1, cid2, distance map(int, input().split())idx1, idx2 idx_map[cid1], idx_map[cid2]dist[idx1][idx2] dist[idx2][idx1] distance# Floyd-Warshall算法 求出所有点之间的最短距离 时间复杂度为O(n^3)
for k in range(n 1):dist[k][k] 0 # 自己到自己的距离为0for i in range(n 1):for j in range(n 1):dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])f [[inf] * (n 1) for _ in range(1 (n 1))]
f[1][0] 0# dp[state][last] 当前情况走过的最短距离
# state 表示已经投递的客户 指定二进制位为1表示已范围last表示上一次投递的客户
dp [[inf] * (n 1) for _ in range(1 (n 1))]
dp[1][0] 0 # 初始状态在投递站for state in range(1 (n 1)):for i in range(n 1):if (state i) 1 and dp[state][i] ! inf: # 如果 i 已经投递 且 可达for last in range(n 1):dp[state | (1 last)][last] min(dp[state | (1 last)][last], dp[state][i] dist[i][last])print(dp[(1 (n 1)) - 1][0])
C
#include iostream
#include vector
#include unordered_map
#include algorithm
#include climitsusing namespace std;int main() {int n, m;cin n m;vectorvectorint dist(n 1, vectorint(n 1, INT_MAX));// 客户id 和索引下标的对照表unordered_mapint, int idxMap;// 初始化客户id 到 投递站(0) 之间的距离for (int idx 1; idx n; idx) {int cid, distance;cin cid distance;dist[0][idx] dist[idx][0] distance;idxMap[cid] idx;}// 初始化客户与客户之间的距离for (int i 0; i m; i) {int cid1, cid2, distance;cin cid1 cid2 distance;int idx1 idxMap[cid1], idx2 idxMap[cid2];dist[idx1][idx2] dist[idx2][idx1] distance;}// Floyd-Warshall算法 求出所有点之间的最短距离 时间复杂度为O(n^3)for (int k 0; k n; k) {dist[k][k] 0; // 自己到自己的距离为0for (int i 0; i n; i) {for (int j 0; j n; j) {dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]);}}}// dp[state][last] 当前情况走过的最短距离// state 表示已经投递的客户 指定二进制位为1表示已经投递last表示上一次投递的客户vectorvectorint dp(1 (n 1), vectorint(n 1, INT_MAX));dp[1][0] 0; // 初始状态在投递站for (int state 0; state (1 (n 1)); state) {for (int i 0; i n; i) {if ((state i 1) 1 dp[state][i] ! INT_MAX) { // 如果 i 已经投递 且 可达for (int last 0; last n; last) {dp[state | (1 last)][last] min(dp[state | (1 last)][last], dp[state][i] dist[i][last]);}}}}cout dp[(1 (n 1)) - 1][0] endl;return 0;
}
相关练习题
题号题目难易LeetCode 29762976. 转换字符串的最小成本 I中等 ❤️华为OD机试面试交流群每日真题分享 加V时备注“华为od加群” 整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
