怎么让网站被收录,文章一键导入wordpress,西宁网站建设模板,网站建设市场调研框架7-8 旅行售货员
某售货员要到若干城市去推销商品#xff0c;已知各城市之间的路程(或旅费)。他要选定一条从驻地出发#xff0c;经过每个城市一遍#xff0c;最后回到驻地的路线#xff0c;使总的路程#xff08;或总旅费#xff09;最小。
输入格式:
第一行为城市数n…7-8 旅行售货员
某售货员要到若干城市去推销商品已知各城市之间的路程(或旅费)。他要选定一条从驻地出发经过每个城市一遍最后回到驻地的路线使总的路程或总旅费最小。
输入格式:
第一行为城市数n
下面n行n列给出一个完全有向图如 i 行 j 列表示第 i 个城市到第 j 个城市的距离。
输出格式:
一个数字表示最短路程长度。
输入样例:
3
0 2 1
1 0 2
2 1 0输出样例:
3简化版代码
解释下面这个代码是没有进行剪枝的也就是说没有优化但是可以过pta所以我也给出
#include iostreamconst int N 20;bool vis[N];
int n, mp[N][N], ans 0x3f3f3f3f;void dfs(int u, int siz, int fee)
{for (int i 0; i n; i) {if (i u || vis[i]) continue;vis[i] true;dfs(i, siz 1, fee mp[u][i]);vis[i] false;}
}int main()
{scanf(%d, n);for (int i 0; i n; i)for (int j 0; j n; j)scanf(%d, mp[i][j]);dfs(0, 0, 0);printf(%d, ans);return 0;
}解释这个代码是在上面这个代码的基础上加上了剪枝的代码也就是优化了一下如果只是为了过pta用上面这份代码就够了
这个是优化的部分代码 if (siz n ans fee) {ans fee;}if (fee ans || siz n) return ;if (siz n - 1 vis[0]) return ;完整代码
#include iostreamconst int N 20;bool vis[N];
int n, mp[N][N], ans 0x3f3f3f3f;void dfs(int u, int siz, int fee)
{if (siz n ans fee) {ans fee;}if (fee ans || siz n) return ;if (siz n - 1 vis[0]) return ;for (int i 0; i n; i) {if (i u || vis[i]) continue;vis[i] true;dfs(i, siz 1, fee mp[u][i]);vis[i] false;}
}int main()
{scanf(%d, n);for (int i 0; i n; i)for (int j 0; j n; j)scanf(%d, mp[i][j]);dfs(0, 0, 0);printf(%d, ans);return 0;
}注释版代码
#include iostreamconst int N 20;bool vis[N];
int n, mp[N][N], ans 0x3f3f3f3f;// 深度优先搜索函数
void dfs(int u, int siz, int fee)
{// 如果已经找到了一种方案且费用更低更新答案if (siz n ans fee) {ans fee;}// 如果当前费用已经超过当前答案或者已经选择了足够的点结束递归if (fee ans || siz n) return;// 如果还需要选择一个点但是第一个点已经被选中结束递归if (siz n - 1 vis[0]) return;// 遍历所有未被选择的点for (int i 0; i n; i) {if (i u || vis[i]) continue;// 选择一个点并递归vis[i] true;dfs(i, siz 1, fee mp[u][i]);// 恢复状态回溯vis[i] false;}
}int main()
{// 输入点的数量scanf(%d, n);// 输入图的邻接矩阵for (int i 0; i n; i)for (int j 0; j n; j)scanf(%d, mp[i][j]);// 从第一个点开始进行深度优先搜索dfs(0, 0, 0);// 输出最小费用printf(%d, ans);return 0;
}java版代码
import java.util.Scanner;public class Main {static final int N 20;static boolean[] vis new boolean[N];static int[][] mp new int[N][N];static int n, ans Integer.MAX_VALUE;// 深度优先搜索函数static void dfs(int u, int siz, int fee) {// 如果已经找到了一种方案且费用更低更新答案if (siz n ans fee) {ans fee;}// 如果当前费用已经超过当前答案或者已经选择了足够的点结束递归if (fee ans || siz n) return;// 如果还需要选择一个点但是第一个点已经被选中结束递归if (siz n - 1 vis[0]) return;// 遍历所有未被选择的点for (int i 0; i n; i) {if (i u || vis[i]) continue;// 选择一个点并递归vis[i] true;dfs(i, siz 1, fee mp[u][i]);// 恢复状态回溯vis[i] false;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 输入点的数量n scanner.nextInt();// 输入图的邻接矩阵for (int i 0; i n; i) {for (int j 0; j n; j) {mp[i][j] scanner.nextInt();}}// 从第一个点开始进行深度优先搜索dfs(0, 0, 0);// 输出最小费用System.out.println(ans);}
}
