我的编程空间,编程开发者的网络收藏夹
学习永远不晚

JavaScript中dis[i][j][u]怎么算

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

JavaScript中dis[i][j][u]怎么算

这篇“JavaScript中dis[i][j][u]怎么算”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“JavaScript中dis[i][j][u]怎么算”文章吧。

一看数据规模,n≤12,果断状压。

然后起点要枚举,就设dp状态:

f[i][j]=以i为起点到j状态的最小花费

其中j是一个二进制数(用十进制来表示)第i位的1、0分别表示是否已经到达第i点(1表示已经到达,0表示还未到达)

(因为m很大,n很小,会有重边,所以用邻接矩阵(e[u][v]))

由此可以列出状态转移方程:

f[i][j]=min{f[i][k]+diss[i][k][u]*e[u][v]}

(j&(1<<(u-1))!=0,j&(1<<(v-1))!=0,i!=v,k=j^(1<<(v-1)),e[u][v]!=1e9)

(e[u][v]!=1e9说的就是u、v之间有边)

什么意思?就是说我们再找一个状态(k)比当前状态(j)只少一个点(显然不能是起点),然后从k向j拓展,在所有的k中取花费最少的那种。

但是还有一个问题,该边的花费怎么算?

根据题目描述,就将该边长度乘上起点到uu经过的点数(dis[i][j][u])即可。

问题又来了,dis[i][j][u]怎么算?

每次状态转移的时候顺便转移一下即可

代码如下:

#include<cstdio>

inline int read(){
	int r=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r*f;
}

int n,ans=1e9,m,f[15][5005],e[15][15],dis[15][5005][15];

inline int min(int a,int b){
	return a<b?a:b;
}

int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			e[i][j]=1e9;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		if(u-v)e[u][v]=e[v][u]=min(e[u][v],read());
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<1<<n;j++)
			f[i][j]=1e9;
	for(int i=1;i<=n;i++){
		f[i][1<<(i-1)]=0;
		dis[i][1<<(i-1)][i]=1;
		for(int j=(1<<(i-1))+1;j<1<<n;j++){
			if(!(j&(1<<(i-1))))continue;
			int x=j,u=1;
			while(x){
				if(x&1){
					for(int v=1;v<=n;v++){
						if(i==v||e[u][v]==1e9||!(j&(1<<(v-1))))continue;
						int k=j^(1<<(v-1));
						if(f[i][j]>f[i][k]+dis[i][k][u]*e[u][v]){
							f[i][j]=f[i][k]+dis[i][k][u]*e[u][v];
							for(int y=1;y<=n;y++)dis[i][j][y]=dis[i][k][y];
							dis[i][j][v]=dis[i][k][u]+1;
						}
					}
				}
				u++;
				x>>=1;
			}
		}
		ans=min(ans,f[i][(1<<n)-1]);
	}
	printf("%d",ans);
	return 0;
}

以上就是关于“JavaScript中dis[i][j][u]怎么算”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注编程网行业资讯频道。

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

JavaScript中dis[i][j][u]怎么算

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

javascript中循环次数怎么算

在JavaScript中,循环语句是经常被用到的语句之一。循环语句就是重复执行一段代码块,直到满足某个条件为止,这个条件可以是值等于某个指定的值,或者某个布尔表达式为真等等。在使用循环语句时,我们需要考虑到循环的次数,因为循环次数的多少可能会影响到程序的运行效率。JavaScript中的循环语句有for、while和do-while循环。其中,for循环是最常用的一种。在for
2023-05-14

JavaScript中逗号运算符怎么用

这篇文章将为大家详细讲解有关JavaScript中逗号运算符怎么用,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。逗号运算符逗号运算符( ,)用来评估其每个操作数(从左到右)并返回最后一个操作数的值。let
2023-06-27

javascript中instanceof运算符怎么使用

在JavaScript中,instanceof运算符用于检查一个对象是否是某个构造函数的实例。它的使用方法如下:```javascriptobject instanceof constructor```其中,`object`是要检查的对象,
2023-08-12

怎么在JavaScript中使用三元运算符

本篇文章给大家分享的是有关怎么在JavaScript中使用三元运算符,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。JavaScript可以做什么1.可以使网页具有交互性,例如响
2023-06-14

怎么在javascript中使用相等运算符

这篇文章给大家介绍怎么在javascript中使用相等运算符,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。1、相等运算符比较不严格。如果两个操作数量不是同一种类型,那么相等运算符就试着进行一些类型的转换,然后进行比较。
2023-06-15

javascript中怎么提高扩展运算符的性能

这篇“javascript中怎么提高扩展运算符的性能”文章,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要参考一下,对于“javascript中怎么提高扩展运算符的性能”,小编整理了以下知识点,请大家跟着小编的步伐一
2023-06-06

怎么在JavaScript中使用switch语句计算指定日期

今天就跟大家聊聊有关怎么在JavaScript中使用switch语句计算指定日期,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。JavaScript可以做什么1.可以使网页具有交互性,
2023-06-14

利用JavaScript怎么对购物车中商品的总价进行计算

本篇文章为大家展示了利用JavaScript怎么对购物车中商品的总价进行计算,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。Java的特点有哪些Java的特点有哪些1.Java语言作为静态面向对象编程
2023-06-07

怎么在Java中使用JavaScript实现一个字符串计算器功能

本篇文章为大家展示了怎么在Java中使用JavaScript实现一个字符串计算器功能,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。代码如下:package scc;import javax.scri
2023-05-30

编程热搜

目录