您好,登錄后才能下訂單哦!
這篇“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]怎么算”這篇文章的內容,相信大家都有了一定的了解,希望小編分享的內容對大家有幫助,若想了解更多相關的知識內容,請關注億速云行業資訊頻道。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。