首页 > 其他分享 >249 旅行商

249 旅行商

时间:2024-11-06 14:49:16浏览次数:2  
标签:旅行 ai 城市 蜗蜗 int include 249 dp




/*

http://oj.daimayuan.top/course/5/problem/249

蜗蜗的世界里有 n 
 个城市,城市两两之间通过高速公路连接,从第 i
 个城市走到第 j
 个城市需要花费 ai,j
 的时间。

现在蜗蜗想从 1 号城市出发旅游,他想把每个城市都玩个遍,但又不想在一个城市玩两遍,玩完以后蜗蜗需要回到 1 号城市应付期末考试。请问蜗蜗最少需要花费多少时间?

蜗蜗到了一个城市以后,一定会在这个城市游玩。蜗蜗在出发之前会先在 1 号城市游玩。连接两个城市的高速公路不会经过其他城市。由于路况的原因,从第 i
 个城市走到第 j
 个城市花费的时间不一定等于从第 j
 个城市走到第 i
 个城市花费的时间。

输入格式
第一行一个整数 n
 表示城市数目。

接下来 n
 行,每行 n
 个整数。第 i
 行第 j
 列的整数表示 ai,j
。

输出格式
一行一个整数表示答案。

样例输入
2
0 1
2 0
样例输出
3
数据范围
对于 100%
 的数据,保证 2≤n≤18
,如果 i=j
,则 ai,j=0
,否则 1≤ai,j≤10000。
*/


#include <iostream>
#include <algorithm>
#include <cstring>



using namespace std;


const int N = 20;
int dp[N][1 << N];

int n;
int mm[N][N];

bool isIn(int st, int a) {
	if (st & (1 << a)) return true;
	return false;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mm[i][j];
		}
	}

	memset(dp, 0x3f, sizeof dp);
	for (int i = 1; i < n; i++) {
		dp[i][1 << i] = mm[0][i];
	}
	int ans = 0x3f3f3f3f;
	for (int st = 0; st < (1 << n); st++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if ( !isIn(st, j) &&  isIn(st, i)) {
					dp[j][st | (1 << j)] = min(dp[j][st | (1 << j)], dp[i][st] + mm[i][j]);
				}
				if (j == 0 && (st | (1 << j)) == (1 << n) - 1) {
					ans = min(ans, dp[j][st | (1 << j)]);
				}
			}
		}
	}


	cout << ans << endl;


	return 0;
}

标签:旅行,ai,城市,蜗蜗,int,include,249,dp
From: https://www.cnblogs.com/itdef/p/18530185

相关文章

  • 《文通护照阅读器:旅行社的高效助手》
    在当今快节奏的旅游时代,旅行社作为连接游客与世界各地的桥梁,不断寻求更高效、更便捷的工具来提升服务质量和工作效率。而文通护照阅读器的出现,无疑为旅行社带来了一场变革。一、传统旅行社业务的挑战在过去,旅行社的工作人员在处理游客的护照信息时,往往需要手动录入,这是一......
  • CF1249F Maximum Weight Subset 题解 / 长链剖分复习
    CF1249FMaximumWeightSubset题解题目大意给定一个\(n\)个节点的树,每个节点有点权\(a_i\)。从中选出若干节点,要求这些点两两之间距离大于给定常数\(k\),使得点权和最大。Solve给出一种线性做法。前置知识:长链剖分优化DP。考虑一个DP:设\(f(u,d)\)表示在\(u\)的子......
  • 基于SSM爱旅行平台的设计与实现
    前言对于当今社会的人们来说,互联网技术是必不可少的,随着经济和技术的不断发展,计算机已经深入到各个领域。爱旅行平台将人们的时间需求与计算机技术结合起来,架起一座桥梁,使爱旅行平台更加方便快捷。爱旅行平台主要为人们提供系统化、个性化、专业化的服务,以提高人们的愉悦感......
  • 基于SpringBoot+Vue旅行推广网站的设计与实现
    博主主页:一季春秋博主简介:专注Java技术领域和毕业设计项目实战、Java、微信小程序、安卓等技术开发,远程调试部署、代码讲解、文档指导、ppt制作等技术指导。主要内容:SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、小程序、安卓app、大数据等设计与开发。感兴趣的可......
  • 去哪儿旅行携手 HarmonyOS SDK | 告别繁琐,常用信息秒级填充
    背景去哪儿旅行作为行业内领先的一站式在线旅游平台,多年来在日益加剧的市场竞争中积极寻求创新,凭借其优质的服务深受消费者青睐。2024年,去哪儿旅行适配HarmonyOSNEXT版本,升级用户服务体验。当前,去哪儿旅行应用中多个业务服务涉及表单填充场景。用户在进行身份信息填写,尤其是同......
  • 星际迷航:人类距离实现太空旅行还有多远?
    内容概要人类的太空旅行梦,仿佛是一颗璀璨的星星,高悬于夜空,既让人憧憬,又充满了不确定性。为了更接近这颗星星,科学家们不断探索各类理论,其中最引人注目的便是曲速飞行。这种飞行方式据说可以让宇宙飞船在不触犯光速限制的情况下,快速穿越浩瀚星际,仿佛给旅行者装上了一双隐形的翅......
  • (附源码)Node.JS 校园失物招领小程序 毕业设计66249
    摘 要随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,微信小程序的校园失物招领系统被用户普遍使用,为方便用户能够可以随时进行微信小程序的校园失物招领系统的数据信息管理。......
  • 【题解】[2023 合肥蜀山初中] 旅行(travel)
    题目传送门题目大意有一个\(n\)个点\(m\)条边的有向图组成的城市,每条边可以是骑行边或公共交通边,公共交通边只能走一条,边是从\(u_i\)到\(v_i\)的有向边,需要花费\(time_i\)的时间,求\(1\)到其他点的最短路径。思路分析有一个很巧妙的思路叫分层图,它的思路是因为只能......
  • 约80%开发效率提升,原生鸿蒙政务、文旅行业样板间专区上线
    10月8日,华为官方正式宣布,其最新操作系统HarmonyOSNEXT于当日10:08正式开启公测。为有效助力开发者加速行业应用开发,华为开发者联盟生态市场(简称生态市场)近日上线了原生鸿蒙政务行业、文旅行业“样板间”专区。政务和文旅行业作为数字化转型的重要领域,对数智应用的需求日益专业化......
  • 题解:P9743 「KDOI-06-J」旅行
    ProblemLink「KDOI-06-J」旅行题意题目讲的很清楚,不再过多赘述。Solution不难想到\(O(n^2\timesm^2\timesk)\)的做法:定义\(f_{i,j,val,x,y}\)为当前在\((x,y)\)的位置,花费\(val\)元,手上有\(x\)张\(L\)公司的票,\(y\)张\(Z\)公司的票的方案数,至于空间问题......