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

這篇“JavaScript中dis[i][j][u]怎么算”文章的知識點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“JavaScript中dis[i][j][u]怎么算”文章吧。

一看數(shù)據(jù)規(guī)模，n≤12，果斷狀壓。

然后起點(diǎn)要枚舉，就設(shè)dp狀態(tài)：

f[i][j]=以i為起點(diǎn)到j(luò)狀態(tài)的最小花費(fèi)

其中j是一個二進(jìn)制數(shù)（用十進(jìn)制來表示）第i位的1、0分別表示是否已經(jīng)到達(dá)第i點(diǎn)（1表示已經(jīng)到達(dá)，0表示還未到達(dá)）

（因?yàn)閙很大，n很小，會有重邊，所以用鄰接矩陣（e[u][v]））

由此可以列出狀態(tài)轉(zhuǎn)移方程：

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之間有邊）

什么意思？就是說我們再找一個狀態(tài)（k）比當(dāng)前狀態(tài)（j）只少一個點(diǎn)（顯然不能是起點(diǎn)），然后從k向j拓展，在所有的k中取花費(fèi)最少的那種。

但是還有一個問題，該邊的花費(fèi)怎么算？

根據(jù)題目描述，就將該邊長度乘上起點(diǎn)到uu經(jīng)過的點(diǎn)數(shù)（dis[i][j][u]）即可。

問題又來了，dis[i][j][u]怎么算？

每次狀態(tài)轉(zhuǎn)移的時候順便轉(zhuǎn)移一下即可

代碼如下：

#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;
}

以上就是關(guān)于“JavaScript中dis[i][j][u]怎么算”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。