首页 > 试题广场 >

毕业旅行问题

[编程题]毕业旅行问题
  • 热度指数：14781 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

输入描述:
城市个数n（1<n≤20，包括北京）

城市间的车票价钱 n行n列的矩阵 m[n][n]


输出描述:
最小车费花销 s
示例1

输入

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出

13

说明

共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。
算法知识视频讲解
开通博客
头像 vaee
发表于 2021-08-10 15:07:27
分析： 假设有0,1,2,3四个城市，起点不会影响结果，因此选城市0为起点，创建一个二维数组dp[][]，用二维数组元素的值代表最低花费，用行坐标代表起点城市，列坐标代表接下来要去的城市（注列坐标用二进制表示，如接下来去1,3城市，则使二进制数第一三位为1，即用101表示）。 因此 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 小牛冲冲冲jiang
发表于 2021-09-21 06:41:06
最优子结构证明 https://blog.csdn.net/qq_39559641/article/details/101209534写的不错 简简单单 import javax.swing.text.Style; import java.util.Scanner; import java.util 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 offer神附体
发表于 2024-04-13 21:17:20
描述小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。输入描述：城市 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 神奇的老王
发表于 2023-11-04 22:00:33
一、参考文献 前置知识（动态规划入门）：《挑战程序设计竞赛》P51 - P69 基础知识（集合整数表示）：《挑战程序设计竞赛》P156 - P158 算法详解（状态压缩的DP）：《挑战程序设计竞赛》P191 - P193 二、基于递归实现（易于理解） #include <iostream> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 大厂算法岗必拿下
发表于 2021-09-20 05:04:47
经典TF问题 #include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ vector<vector<int>> dis 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 重生之我要当分子
发表于 2025-01-03 12:44:56
解题思路 这是一个经典的旅行商问题(TSP)。需要找到从起点出发，经过所有城市一次后返回起点的最小花费路径。 关键点： 使用状态压缩DP解决 用二进制表示城市的访问状态 记录当前所在城市和已访问城市 需要考虑回到起点的花费 算法步骤： 初始化DP数组，记录状态和花费 遍历所有可能的城市访问状态 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2023-12-20 16:59:39
import java.util.*; public class Main { private static int N; private static int[][] price; private static boolean[] visited; private 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 算法工程师 队列 测试工程师 PHP工程师 查找 动态规划 抖音信息 2019 Java工程师
上传者：小小
难度：
64条回答 28521浏览

热门推荐

通过挑战的用户

查看代码

相关试题

毕业旅行问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号