poj3311 Hie with the Pie

题目链接:https://vjudge.net/problem/POJ-3311

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

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

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

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

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

  

上一篇:AcWing 最短哈密顿路径(状态压缩dp)


下一篇:Tensorflow Lite模型部署实战教程--选择合适的DelegateProviders委托提供者