n个点,起点不定,每个点最多经过2次,问走完所有点最小花费
和poj3311相似,所以我一开始就按着poj3311的方法来做的,WA了一晚上......
后来发现是用了弗洛伊德预处理了两点的最短距离,这错了
不能预处理,poj3311要预处理,那是因为没有经过次数的限制,但这有,弗洛伊德预处理出的最短距离时,可能是经过了某些点而得到的,而我又没记录哪些点经过了,,,,
三进制的状态DP
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int three[]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441};
#define INF ~0U>>2
int n,m;
int a,b,c;
int dis[12][12];
int dp[59049+10][12];
inline int get(int i,int j)//i的第j位
{
return i%three[j+1]/three[j];
}
inline int getOld(int i,int j)//i的第j位减1
{
return i-three[j];
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dis[i][j]=(i==j?0:INF);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
a--,b--;
if(dis[a][b]>c)
{
dis[a][b]=dis[b][a]=c;
}
}
for(int i=0;i< three[n];i++)
for(int j=0;j<n;j++)
dp[i][j]=INF;
for(int i=0;i<n;i++)
{
dp[three[i]][i]=0;
}
for(int i=0;i<three[n];i++)
{
for(int j=0;j<n;j++)
{
int k=get(i,j);
if(k==0) continue;
else
{
for(int r=0;r<n;r++)
{
int kk=get(i,r);
if(kk==0) continue;
if(r==j) continue;
int sta=getOld(i,j);
dp[i][j]=min(dp[i][j],dp[sta][r]+dis[r][j]);
}
}
}
}
int ans=INF;
for(int j=0;j< three[n];j++)
{
int tag=1;
for(int i=0;i<n;i++)
{
if(get(j,i)==0)
{
tag=0;break;
}
}
if(tag)
{
for(int i=0;i<n;i++)
{
ans=min(ans,dp[j][i]);
}
}
}
printf("%d\n",ans==INF?-1:ans);
}
}