题解

全部评论 1

• 

  一只小黑子ด้้้้้（章奕凡）

  

  格式不好，帮你改一下：

  #include <bits/stdc++.h>
  using namespace std;
  const int Max=5000;
  const int inf=1e9;
  int n,m,ans=1e9,tot;
  int dis[20][20],f[20][Max];
  int p[Max],num[Max],pos[Max],sum[Max],condition[Max];
  inline int get_int(){
      int x=0,f=1;
      char c;
      for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
      if(c=='-'){f=-1;c=getchar();}
      for(;isdigit(c);c=getchar()){
          x=(x<<3)+(x<<1)+c-'0';
      }
      return x*f;
  }
  inline int mn(int x,int y){
      return x<y?x:y;
  }
  int main(){
      n=get_int(),m=get_int();
      memset(f,0x3f,sizeof(f));
      for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
              dis[i][j]=10000000;
          }
      }
      for(int i=1;i<=m;i++){
          int x=get_int()-1,y=get_int()-1,z=get_int();
          dis[x][y]=dis[y][x]=mn(z,dis[x][y]);
      }
      for(int i=0;i<n;i++){
          pos[1<<i]=i,f[0][1<<i]=0;
      }
      for(int i=0;i<n;i++){
          for(int j=0;j<(1<<n);j++){
              tot=0;
              for(int to=0;to<n;to++){
                  if((1<<to)&j){
                      continue;
                  }
                  p[tot]=1<<to;
                  num[tot]=10000000;
                  for(int k=j;k;k-=k&(-k)){
                      int from=pos[k&(-k)];
                      num[tot]=mn(num[tot],dis[from][to]*(i+1));
                  }
              tot++;
              }
              for(int k=1;k<(1<<tot);k++){
                  condition[k]=condition[k-(k&(-k))] | p[pos[k&(-k)]];
                  sum[k]=sum[k-(k&(-k))] + num[pos[k&(-k)]];
                  f[i+1][j|condition[k]]=mn(f[i+1][j|condition[k]],f[i][j]+sum[k]);
              }
          }
      }
      for(int i=0;i<=n;i++){
          ans=mn(ans,f[i][(1<<n)-1]);
      }
      cout<<ans<<"\n";
      return 0;
  }
  

  2024-07-23 来自 上海

  0