3311 -- Hie with the Pie (poj.org)
Pizazz披萨店以尽可能快地将披萨送到顾客手中而自豪。
不幸的是，由于削减开支，他们只能雇一个司机来送货。
司机将等待 1 个或更多 (最多10个) 订单被下达后再开始送餐。
不用说，他想要走最短的路线来运送这些食物并返回披萨店，即使这意味着在途中不止一次地经过同一地点或披萨店。
他委托你写一个程序来帮助他。
输入将由多个测试用例组成。
请注意，由于不同的速度限制，交通信号灯等，经过其他位置的中转，可能实现更快地从 i 到 j。
此外，时间值可能不对称，即直接从位置 i 到 j 的时间可能与直接从位置 j 到 i 的时间不相同。
输入值 n = 0 将终止输入。
对于每个测试用例，您应该输出单个数字，指示交付所有披萨并返回披萨店所需的最短时间。
| 输入 | 3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 0 |
| 输出 | 8 |
| 说明 | 无 |
本题第二行~倒数第二行的输入其实就是一个 (n+1) * (n+1) 的邻接矩阵，我们定义其为dist矩阵。
dist[i][j] 表示客户位置 i 到 客户位置 j 的距离。
本题需要我们帮助司机找到一条最短路径，该最短路径需要满足：
首先，这题需要我们经过所有客户位置，因此我们对 1~n 客户位置求解全排列，每一个全排列即代表一种送餐策略路径，比如n=3，则有以下送餐策略路径：
我们在这些全排列首尾加上0，即可得所有送餐策略路径：
由于本题的?1 ≤ n ≤ 10 ，因此全排列求解不会超时。
得到所有的送餐策略路径后，我们需要求解每种策略路径对应的送餐距离，
如果想要每种策略的送餐距离尽可能小，则我们应该保证路径中相邻两点之间的距离尽可能的小。
而求解图中任意两点间的最短距离，最佳策略是使用floyd算法。
关于floyd算法可以看下：最短路径算法全套(floyed+dijstra+Bellman+SPFA)_哔哩哔哩_bilibili
最终，我们基于floyd算法，求得上面每个全排列路径的最短距离，在这些最短距离中最小的即为题解。
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
while (true) {
const n = parseInt(await readline());
if (n == 0) break;
// floyd算法需要基于dist和path矩阵求解
// dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵
const dist = [];
// path[i][j] 用于记录点 i->j 最短距离情况下需要经过的中转点，初始时默认任意两点间无中转点，即默认path[i][j] = -1
const path = [];
for (let i = 0; i < n + 1; i++) {
dist.push((await readline()).split(" ").map(Number));
path.push(new Array(n + 1).fill(-1));
}
// 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;
}
}
}
})();
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);
while (sc.hasNextInt()) {
n = sc.nextInt();
if (n == 0) break;
// 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++) {
dist[i][j] = sc.nextInt();
path[i][j] = -1;
}
}
// 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;
}
}
}
import sys
# 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
while True:
n = int(input())
if n == 0:
break
# floyd算法需要基于dist和path矩阵求解
# dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵
dist = [list(map(int, input().split())) for _ in range(n + 1)]
# path[i][j] 用于记录点 i->j 最短距离情况下需要经过的中转点，初始时默认任意两点间无中转点，即默认path[i][j] = -1
path = [[-1] * (n + 1) for _ in range(n + 1)]
# floyd算法调用
floyd()
# ans记录经过所有点后回到出发点的最短距离
ans = sys.maxsize
# 全排列模拟经过所有点的路径
dfs(0, 0, [False] * (n + 1), 0)
print(ans)
POJ的C编译器估计有点老了，很多语法和内置库都无法用，下面是适配修改后可以AC的代码
#include <stdio.h>
#include <limits.h>
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX_SIZE 11
int n;
int dist[MAX_SIZE][MAX_SIZE];
int path[MAX_SIZE][MAX_SIZE];
int ans;
int used[MAX_SIZE];
/**
* 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同 //
* 求某个全排列过程中，可以通过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) {
int i;
if (level == n) {
// 此时pre是最后一个客户所在点，送完最后一个客户后，司机需要回到披萨店，因此最终累计路径权重为 sum + dist[pre][0]
// 我们保留最小权重路径
ans = MIN(ans, sum + dist[pre][0]);
return;
}
for (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() {
int i, j, k;
for (k = 0; k < n + 1; k++) {
for (i = 0; i < n + 1; i++) {
for (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() {
while (1) {
int i, j;
scanf("%d", &n);
if (n == 0) {
break;
}
// floyd算法需要基于dist和path矩阵求解
for (i = 0; i < n + 1; i++) {
for (j = 0; j < n + 1; j++) {
// dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵
scanf("%d", &dist[i][j]);
// path[i][j] 用于记录点 i->j 最短距离情况下需要经过的中转点，初始时默认任意两点间无中转点，即默认path[i][j] = -1
path[i][j] = -1;
}
}
// floyd算法调用
floyd();
// ans记录经过所有点后回到出发点的最短距离
ans = INT_MAX;
// 全排列模拟经过所有点的路径
for (i = 0; i < n + 1; i++) used[i] = 0;
dfs(0, 0, used, 0);
printf("%d\n", ans);
}
}