用dp[i]来表示状态i下的最优方案,dis[j]表示j到根节点的距离（题目中所描述的K）用dfs来更新答案
#include<bits/stdc++.h> #include<cstdio> #define INF 2139062143 #define N 12 #define M 1005 using namespace std; int g[N][N],n,m,dis[N],f[(1<<N)+10]; inline void update(int x,int y,int z) { g[x][y]=z; g[y][x]=z; } void dfs(int s) { for(int i=1;i<=n;i++) { if((1<<(i-1))&s) { for(int j=1;j<=n;j++) { if(g[i][j]!=INF&&!((1<<(j-1))&s)) { if(f[1<<(j-1)|s]>f[s]+dis[i]*g[i][j]) { dis[j]=dis[i]+1; f[1<<(j-1)|s]=f[s]+dis[i]*g[i][j]; dfs(1<<(j-1)|s); dis[j]-=1; } } } } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=INF; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; if(z<g[x][y]) update(x,y,z); } int ans=INF; for(int i=1;i<=n;i++) //枚举起点 { memset(dis,127,sizeof(dis)); memset(f,127,sizeof(f)); dis[i]=1; f[1<<(i-1)]=0; dfs(1<<(i-1)); ans=min(ans,f[(1<<n)-1]); } cout<<ans<<endl; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9803513.html
