(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("%dn", ans);
}