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]怎么算？

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

代码如下：

#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]怎么算"这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注行业资讯频道。