扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
这篇“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]怎么算?
每次状态转移的时候顺便转移一下即可
代码如下:
#includeinline 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 af[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< 以上就是关于“JavaScript中dis[i][j][u]怎么算”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注创新互联行业资讯频道。
网页名称:JavaScript中dis[i][j][u]怎么算
文章链接:http://kswjz.com/article/igpiid.html
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流