poj3311 Hie with the Pie

题目链接:<https://vjudge.net/problem/POJ-3311&gt;

题意:从0点出发,每个点至少走一次,最后回到0点,求最短长度

相比tsp问题的不同之处是每个点可以走超过一次。这个条件的效果是,假如直接相连的两点间有一条很长的边w,可能存在另外一条路,重复走过了某个点,使得两点距离<w。这样只要求出两两点对之间的最短路即可,由于数据很小,使用floyd,然后就是裸的tsp问题

#include&lt;iostream&gt;
#include&lt;algorithm&gt;
#include&lt;cstring&gt;
using namespace std;

int d[15][15],f[15][(1&lt;&lt;15)],n,i,j,k,s,u,v;

int main(){
    while (cin&gt;&gt;n){
      if (n==0) break; n++;
      memset(d,0x3f,sizeof(d));
      memset(f,0x3f,sizeof(f));
      for (i=0;i&lt;n;i++)
        for (j=0;j&lt;n;j++) cin&gt;&gt;d[i][j];
      for (k=0;k&lt;n;k++)
        for (i=0;i&lt;n;i++)
          for (j=0;j&lt;n;j++)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      f[0][1]=0;
      for (s=0;s&lt;(1&lt;&lt;n);s++)
        for (v=0;v&lt;n;v++)
          if (s&amp;(1&lt;&lt;v)){
            for (u=0;u&lt;n;u++)
              if ((u!=v)&amp;&amp;s&amp;(1&lt;&lt;u)) 
                f[v][s]=min(f[v][s],f[u][s^(1&lt;&lt;v)]+d[u][v]);
          }
      int ans=1e9;
      for (i=1;i&lt;n;i++) ans=min(ans,f[i][(1&lt;&lt;n)-1]+d[i][0]);
      cout&lt;&lt;ans&lt;&lt;endl;
    }
    return 0;
} 

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。